题解：CF715E Complete the Permutations

· · 题解

图论建模，看成有 n 个点，每个点有两个权值 p_i 和 q_i，对于点 i、j，若 p_i=q_j \neq 0，则在 i 和 j 之间连边权位 p_i 的边。最少操作数就是 n 减去环的数量（自环也算）。这样就得到了一些环、链（孤立的点可以看成长度为 1 的链）。

对于现有的环，直接去掉，最后输出答案的时候再算进去就行了（记住这句话，后面要用）。

对于链，根据起点 i，终点 j 进行分类，可以分成四类。

对于一个 I 类链，可以将 q_i 和 p_j 缩成一个点（并查集维护）。我们可以这样理解：先把其他链都排好了之后，再把 I 类链插入就行了，反正它的首尾能连的都是固定的，不影响答案。

对于一个 III 类链 a 和 II 类链 b，若 p_a = q_b 也可以缩成一个 IV 类链。

再将环分成三类：只有 II 类链、只有 III 类链、有 IV 链。

只有 II 类链的环

记 c_2、c_3、c_4 为 II、III、IV 类链的个数，f_i 为 II 类点恰好形成 i 个环的方案数，则：

f_i = \sum_{j=i}^{c_2} {c_2 \choose j} {j \brack i} \frac{(c_2 - j + c_4 - 1)!}{(c_4 - 1)!}

这条式子的组合意义是：先选出 j 条链，放入 i 个圆排列中，剩下的 c_2-j 条链，可以选择合并到另一条 II 类链或者 IV 类链中。

特别地，若 c_4=0，则会出现负数的阶乘无法计算，此时的答案为 f_i = {c_2 \brack i}。

只有 III 类链的环

设 g_i 为 III 类点恰好形成 i 个环的方案数，计算和 f 同理，把上面的 c_2 换成 c_3 就行了。

有 IV 链的环

设 h_i 为恰好形成 i 个环，环中都包含 IV 类链的方案数，则：

h_i = {c_4 \brack i} c_4!

这个式子看起来不是很对，并没有考虑 II 类链和 III 类链。其实是没有问题的，因为在上面已经把这些链合并到 IV 链中了。

输出答案

将三个函数卷积起来，最少操作数就是 (f*g*h)(n-i - \text{cnt})，\text{cnt} 为一开始现有的环数。

#include<bits/stdc++.h>
using namespace std;
const int M=998244353;
int n,a[2005],b[2005],to[2005],in[2005];
int fa[2005];
int find(int x) {
    return fa[x]==x?x:fa[x]=find(fa[x]);
}
void merge(int x, int y) {
    x=find(x), y=find(y), fa[x]=y;
}
int pow(int x, int y) {
    int res=1;
    while(y) {
        if(y&1) res=1ll*res*x%M;
        x=1ll*x*x%M;
        y>>=1;
    }
    return res;
}
int vis[2005],cnt,c2,c3,c4,jc[2005],jcinv[2005],s[2005][2005];
void init() {
    jc[0]=1;
    for(int i=1; i<=2000; i++) jc[i]=1ll*jc[i-1]*i%M;
    jcinv[2000]=pow(jc[2000],M-2);
    for(int i=2000; i>=1; i--) jcinv[i-1]=1ll*jcinv[i]*i%M;
    s[0][0]=1;
    for(int i=1; i<=2000; i++)
        for(int j=1; j<=i; j++)
            s[i][j]=(s[i-1][j-1]+1ll*s[i-1][j]*(i-1))%M;
}
int C(int x, int y) {
    return 1ll*jc[x]*jcinv[x-y]%M*jcinv[y]%M;
}
int A(int x, int y) {
    return 1ll*jc[x]*jcinv[x-y]%M;
}
void init2() {
    // 缩点
    for(int i=1; i<=n; i++) fa[i]=i;
    for(int i=1; i<=n; i++) {
        if(a[i] && b[i]) {
            int x=find(a[i]), y=find(b[i]);
            if(x!=y) fa[x]=y;
            else cnt++;
        }
    }
    for(int i=1; i<=n; i++) a[i]=find(a[i]), b[i]=find(b[i]);

    for(int i=1; i<=n; i++) {
        if(a[i] && !b[i]) c2++, vis[a[i]]++; // II 类边
        if(!a[i] && b[i]) c3++, vis[b[i]]++; // III 类边
        if(!a[i] && !b[i]) c4++; // IV 类边
    }
    for(int i=1; i<=n; i++)
        if(vis[i]>=2)
            c2--,c3--,c4++;
}
int f[2005],g[2005],h[2005],fg[2005],fgh[2005];
int main() {
    init();
    cin>>n;
    for(int i=1; i<=n; i++) cin>>a[i];
    for(int i=1; i<=n; i++) cin>>b[i];
    init2();
//  printf("%d %d %d %d\n",cnt,c2,c3,c4);

    if(c4==0) {
        for(int i=0; i<=c2; i++) f[i]=s[c2][i];
        for(int i=0; i<=c3; i++) g[i]=s[c3][i];
    } else {
        for(int i=0; i<=c2; i++)
            for(int j=i; j<=c2; j++)
                f[i]=(f[i]+1ll*C(c2,j)*s[j][i]%M*A(c4+c2-j-1,c2-j))%M;
        for(int i=0; i<=c3; i++)
            for(int j=i; j<=c3; j++)
                g[i]=(g[i]+1ll*C(c3,j)*s[j][i]%M*A(c4+c3-j-1,c3-j))%M;
    }
    for(int i=0; i<=c4; i++) h[i]=1ll*s[c4][i]*jc[c4]%M;

//  for(int i=0; i<=c2; i++) cout<<f[i]<<' ';
//  cout<<'\n';
//  for(int i=0; i<=c3; i++) cout<<g[i]<<' ';
//  cout<<'\n';
//  for(int i=0; i<=c4; i++) cout<<h[i]<<' ';
//  cout<<'\n';

    for(int i=0; i<=c2; i++)
        for(int j=0; j<=c3; j++)
            fg[i+j]=(fg[i+j]+1ll*f[i]*g[j])%M;
    for(int i=0; i<=c2+c3; i++)
        for(int j=0; j<=c4; j++)
            fgh[i+j]=(fgh[i+j]+1ll*fg[i]*h[j])%M;
    for(int i=0; i<n; i++) {
        if(n-i-cnt>=0) cout<<fgh[n-i-cnt]<<' ';
        else cout<<0<<' ';
    }
    return 0;
}