本文共 1078 字，大约阅读时间需要 3 分钟。
对于n个数组成的序列，求排好序需要最少交换次数的期望次数。
我们可以先求出需要次数总和在乘上 n ! n! n!的逆元
先打一个表，不难发现 f ( n ) = f ( n − 1 ) ∗ n + ( n − 1 ) ( n − 1 ) ! f(n)=f(n-1)*n+(n-1)(n-1)! f(n)=f(n−1)∗n+(n−1)(n−1)! 然后我们在考虑插入，对于前面一个序列，我们可以插入一个比前面的数都大的数进去，之后我们会发现只有插在最后面才不会增加交换次数，其他都会增加一次交换次数，式子显然正确。之后 f f f离线预处理，逆元在线处理
时间复杂度: O ( N + T l o g p ) O(N+T\ \ log\ p) O(N+T log p)#include#include #define p 998244353#define N 10000000#define ll long longusing namespace std;ll t,f[N+10],k,n,jx[N+10];ll read() { int x=0,f=1; char c=getchar(); while(!isdigit(c)) { if(c=='-')f=-f;c=getchar();} while(isdigit(c)) x=(x<<1)+(x<<3)+c-48,c=getchar(); return x*f;}void write(ll x){ if (x>9) write(x/10); putchar(x%10+48); return;}ll power(ll x,ll b)//费马小求逆元{ ll ans=1; while(b) { if(b&1) ans=ans*x%p; x=x*x%p; b>>=1; } return ans;}int main(){ scanf("%lld",&t); f[2]=1;jx[2]=2; for(ll i=3;i<=N;i++)//预处理 { jx[i]=jx[i-1]*i%p;//阶乘预处理 f[i]=(f[i-1]*i%p+(jx[i]-jx[i-1]+p)%p)%p; } for(ll i=1;i<=t;i++) { n=read(); write(power(jx[n],p-2)*f[n]%p); putchar('\n'); }}
转载地址：http://xxzaf.baihongyu.com/