总体而言本题需要用到的技巧有排列组合数、gcd分桶、排列的平均逆序对数。是有点思维量的题目需要不少技巧。1.排列的平均逆序对数想要写出这题应该比较清楚地理解排列的平均逆序对数这一概念。对于一个普通的 n! 排列它的每一组排列的平均逆序对数是意思是以的概率选中一组逆序对这样的逆序对一共有组合数里的n个里面选2个种。对于无附加条件的长度为n的普通排列它的平均逆序对个数是。2.gcd分桶在本题的用处gcd 分桶带来的对称性和排列的平均逆序对数高度相关。gcd 分桶的对称性对于有。也是因为这个对称性所以这也相当于这个和普通随机排列的情况是一致的。所以对于本题的数字 1 至 n-1 都是上面的公式只身下一种特殊情况也就是数字 n 的情况。gcd 分桶可以快速求出的时候有多少个满足条件。这是本题求出合法排列数的方法。3.特殊情况xnkk意思是普通 1 至 n-1 的情况以及减去 xn 的情况的贡献。情况一xn 出现过此时 n 被固定在位置pos因为 n 是最大值它只会和后面的数形成逆序对。产生贡献为n - pos对应代码if(pos) ans*(kk(n-pos)P)%P;情况二xn还没出现此时 n 可以在任意自由位置。设自由位置数量F自由位置下标和S所以 n 的平均位置可以表示为产生贡献为n -对应代码else ans*(kk(n-S%P*inv(F)%P))%P;所以最终答案就是 ans 合法排列数量 × 每组排列的平均期望逆序对数ans * gcd分桶的排列选取情况 *n 未固定时 pos 为已固定时为固定值 pos (保存在这个变量里面)。C代码如下#includebits/stdc.h #define int long long using namespace std; const int P998244353LL; 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(p0)return 1; int kk1;a%P;p%P; while(p1){ if(p%20){ p/2; a*a; a%P; } else{ p--; kk*a; kk%P; } } kk*a;kk%P; return kk; } void Pre(){ for(int i1;in;i)f[i]g[i]h[i]0; for(int gcdn;gcd1;gcd--){ for(int i1;i*gcdn;i){ int ji*gcd; if(f[j]0n%gcd0){ f[j]gcd; g[gcd];h[gcd]; } } } } int inv(int x){ return ksm(x,P-2); } int A(int x,int y){ if(xy||x0||y0)return 0; int ansfac[x]; ans*nifac[y];ans%P; return ans; } signed main(){ ios::sync_with_stdio(false);cin.tie(0); fac[0]nifac[0]1;inv2inv(2);inv4inv(4); for(i1;i2000000;i){ fac[i]fac[i-1]*i;fac[i]%P; nifac[i]inv(fac[i]); } cinT; while(T--){ cinnq;pos0; kk(n*(n-1)%P*inv4%P-(n-1)*inv2%PP)%P; S0;Fn;Pre();anss1; for(i1;in;i)Si; while(q--){ cinix; F--;S-i;if(xn)posi; ansfac[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%PP)%P; coutans\n; } } return 0; }