Codeforces Round 1095 (Div. 2) F. Inversion Invasion
总体而言，本题需要用到的技巧有：排列组合数、gcd分桶、排列的平均逆序对数。是有点思维量的题目，需要不少技巧。
1.排列的平均逆序对数
想要写出这题，应该比较清楚地理解排列的平均逆序对数这一概念。对于一个普通的 n! 排列，它的每一组排列的平均逆序对数是，意思是以
的概率选中一组逆序对，这样的逆序对一共有"组合数里的n个里面选2个"种。
对于无附加条件的长度为n的普通排列，它的平均逆序对个数是。
2.gcd分桶在本题的用处
gcd 分桶带来的对称性，和排列的平均逆序对数高度相关。
gcd 分桶的对称性：对于，有
。
也是因为这个对称性，所以这也相当于，这个和普通随机排列的情况是一致的。所以对于本题的数字 1 至 n-1 都是上面的公式
，只身下一种特殊情况，也就是数字 n 的情况。
gcd 分桶可以快速求出的时候，有多少个
满足条件。这是本题求出合法排列数的方法。
3.特殊情况x==n
kk=，意思是普通 1 至 n-1 的情况，以及减去 x==n 的情况的贡献。
情况一：x=n 出现过
此时 n 被固定在位置：pos
因为 n 是最大值，它只会和后面的数形成逆序对。产生贡献为n - pos
对应代码：
if(pos) ans*=(kk+(n-pos)+P)%P;情况二：x=n还没出现
此时 n 可以在任意自由位置。
设自由位置数量：F
自由位置下标和：S
所以 n 的平均位置可以表示为，产生贡献为n -
对应代码：
else ans*=(kk+(n-S%P*inv(F)%P))%P;所以最终答案就是 ans = 合法排列数量 × 每组排列的平均期望逆序对数
ans =* gcd分桶的排列选取情况 *（
），n 未固定时 pos 为
；已固定时为固定值 pos (保存在这个变量里面)。
C++代码如下：
#include<bits/stdc++.h> #define int long long using namespace std; const int P=998244353LL; int T,n,q,i,x,S,F,inv2,inv4; int f[2000009],g[2000009],h[2000009]; int fac[2000009],nifac[2000009],ans,anss,kk,pos; int ksm(int a,int p){ if(p==0)return 1; int kk=1;a%=P;p%=P; while(p>1){ if(p%2==0){ p/=2; a*=a; a%=P; } else{ p--; kk*=a; kk%=P; } } kk*=a;kk%=P; return kk; } void Pre(){ for(int i=1;i<=n;i++)f[i]=g[i]=h[i]=0; for(int gcd=n;gcd>=1;gcd--){ for(int i=1;i*gcd<=n;i++){ int j=i*gcd; if(f[j]==0&&n%gcd==0){ f[j]=gcd; g[gcd]++;h[gcd]++; } } } } int inv(int x){ return ksm(x,P-2); } int A(int x,int y){ if(x<y||x<0||y<0)return 0; int ans=fac[x]; ans*=nifac[y];ans%=P; return ans; } signed main(){ ios::sync_with_stdio(false);cin.tie(0); fac[0]=nifac[0]=1;inv2=inv(2);inv4=inv(4); for(i=1;i<=2000000;i++){ fac[i]=fac[i-1]*i;fac[i]%=P; nifac[i]=inv(fac[i]); } cin>>T; while(T--){ cin>>n>>q;pos=0; kk=(n*(n-1)%P*inv4%P-(n-1)*inv2%P+P)%P; S=0;F=n;Pre();anss=1; for(i=1;i<=n;i++)S+=i; while(q--){ cin>>i>>x; F--;S-=i;if(x==n)pos=i; ans=fac[F]; anss*=inv(A(g[x],h[x]));anss%=P; h[x]--; anss*=A(g[x],h[x]);anss%=P; ans*=anss;ans%=P; if(pos)ans*=(kk+(n-pos)+P)%P; else ans*=(kk+(n-S%P*inv(F)%P))%P; ans=(ans%P+P)%P; cout<<ans<<'\n'; } } return 0; }