K.atzlein Cocktail

不难发现最少的交换次数就是人数 减去排列形成的环的数量。

先解决 个数完全随机的情况。考虑到排列环中每个点只和两个点相连的特性，我们可以把问题等价于 条相同的绳每次选择两头相连，不生成环的次数的期望。对于一条绳而言，当且仅当他不与自己两头相连时不生成环，而每次合并后可选的绳子必然会减少一条，因此有：。

再来考虑部分数被钦定的情况：如果合并后不形成新环，那么答案增加；而无论是否形成新环，可选的绳子都会减少一条。因此钦定 个数且形成 条新链后的答案为 。

是否形成新环可用并查集解决。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define M 998244353

int i,j,k,n,m,t,fa[500500],res;
ll inv[500500],f[500500];
int find(int x){
    if(fa[x]==x){return x;}
    return fa[x]=find(fa[x]);
}

int main(){
    inv[1]=1;for(int i=2;i<=500000;i++){inv[i]=(M-M/i)*inv[M%i]%M;}
    for(i=1;i<=500000;i++){
        f[i]=(f[i-1]+inv[i]*(i-1))%M;
        fa[i]=i;
    }
    scanf("%d",&n);
    printf("%lld\n",f[n]);
    for(i=1;i<=n;i++){
        scanf("%d",&k);
        if(find(i)!=find(k)){res++;}
        fa[fa[k]]=fa[i];
        printf("%lld\n",(f[n-i]+res+M)%M);
    }
}