Description
给定一个长度为 (n) 的排列，每次可以选择一个子集将它 random_shuffle，并花费子集大小的代价。求将整个排列升序排序的代价期望。
Solution
对于排列 (P)，可以描述为一张图，其中 (i o P_i)，则这张图一定由若干个不交的环构成。我们的任务就是要使得每个环的大小都为 (1)。
结论：每次操作都取一个完整的环不会使答案更劣。
显然环的内容和解决这个环的代价期望没有任何关系，不妨设 (f(n)) 表示解决一个大小为 (n) 的环的期望代价，那么
[f(n)=frac {sum_{i=2}^n C_n^i (i-1)! (n-i)! f(i)} {n!} + n
]
展开化简一下，得到
[f(n)=sum_{i=2}^n frac {f(i)} {i} + n
]
将 (f(n)) 与 (f(n-1)) 的式子做差，变形得到
[f(n) = frac n {n-1} (f(n-1)+1)
]
初态 (f(1)=0, f(2)=4)，暴力递推即可。
在预处理好所有 (f(i)) 后，我们只需要暴力找出每一个环，统计答案即可。
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1000005;
const int mod = 998244353;
int n,m,p[N],vis[N],f[N];
int qpow(int p,int q)
{
return (q&1?p:1)*(q?qpow(p*p%mod,q/2):1)%mod;
}
int inv(int p)
{
return qpow(p,mod-2);
}
void solve()
{
for(int i=1;i<=n;i++) cin>>p[i];
for(int i=1;i<=n;i++) vis[i]=0;
int ans=0;
for(int i=1;i<=n;i++)
{
if(vis[i]) continue;
int x=i,cnt=0;
do
{
++cnt;
vis[x]=1;
x=p[x];
}
while(vis[x]==0);
ans+=f[cnt];
}
cout<<ans%mod<<endl;
}
signed main()
{
ios::sync_with_stdio(false);
cin>>n>>m;
f[1]=0;
f[2]=4;
for(int i=3;i<=n;i++)
{
f[i]=i*inv(i-1)%mod*(f[i-1]+1)%mod;
}
for(int i=1;i<=m;i++)
{
solve();
}
return 0;
}