2020牛客暑期多校训练营（第六场）A African Sort

A African Sort
题意: 给定排列 p，每次可以选一个下标集合等概率打乱包含的数并花费集合大小的代价，求给 p 排升序最优策略下最小代价的期望，对 998244353 取模

做法：一个permutation可以看成若干个环（i连p[i]），显然不存在大小不为1的环即为排序完成。那么对所有大小不为1的环进行随机排序操作，记对大小为n的环进行操作至全部有序的期望花费为f(n)。

对于大小为n的环，随机打乱一共有n!种情况。可以发现，指定i个位置组成一个环，有C(n,i)*(i-1)!*(n-i)!种情况。C(n,i)为指定i个位置的方案数，(i-1)!为指定的i个位置能组成多少种不同的环，即圆排列，(n-i)!为其余n-i个位置任意排列。
所以枚举环的大小i可以得到表达式

$f(n)=\frac{\sum_{i=2}^nC(n,i)*(i-1)!*(n-i)!f(i)}{n!}+n$

化简得到一个带系数的前缀表达式，这里其实也可以维护前缀直接开始做了

$f(n)=\sum_{i=2}^n\frac{f(i)}{i}+n$

但是可以也可以想办法变成逐项递推式，我们有f(n-1)的表达式

$\sum_{i=2}^{n-1}\frac{f(i)}{i}+(n-1)=f(n-1)$

加起来

$f(n)+\sum_{i=2}^{n-1}\frac{f(i)}{i}+(n-1)=f(n-1)+\sum_{i=2}^n\frac{f(i)}{i}+n$

化简得到主递推式

$f(n)=\frac{i(f(n-1)+1)}{i-1}$

再由

$f(2)=\frac{f(2)}{2}+2$

可得到递推边界

$f(2)=4$

到这里就做完了，关键是求这个f函数，贴个代码。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll mod = 998244353;

ll mypow(ll a,ll b){
    ll ret=1;
    while(b){
        if(b&1)ret=ret*a%mod;
        a=a*a%mod;b>>=1;
    }
    return ret;
}

int a[100010],vis[100010];
ll f[100010];
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    f[2]=4;
    for(int i=3;i<100010;i++){
        f[i]=(f[i-1]+1)*i%mod*mypow(i-1,mod-2)%mod;
    }
    int n,m;cin>>n>>m;
    for(int i=1;i<=m;i++){
        for(int i=1;i<=n;i++){
            cin>>a[i];
            vis[i]=0;
        }
        ll ans=0;
        for(int i=1;i<=n;i++){
            if(vis[i])continue;
            vis[i]=1;
            int now=a[i];
            int cnt=1;
            while(now!=i){
                vis[now]=1;
                now=a[now];
                cnt++;
            }
            ans+=f[cnt]%mod;
        }
        cout<<ans%mod<<endl;
    }
}