题目概述

定义两个 $n$ 的排列 $A,B$ 的相似度为通过交换两个元素使得两个排列相同的最小次数。现在给出两个 $n$ 的排列，有些位置还没有确定，求相似度为 $i,i\in[0,n-1)$ 的可能方案数。

解题报告

这是神仙题。首先假设没有 $0$ ，那么从 $a_i$ 向 $b_i$ 连边，不难发现交换一定发生在循环内，所以相似度即 $n-$循环数。

然后考虑 $0$ ，通过缩路径，我们可以把边分成 $0\to 0,0\to B,A\to 0,A\to B$ 以及自带的循环。显然自带的循环以及 $A\to B$ 都不需要考虑，所以我们只要关注 $0\to 0,0\to B,A\to 0$ 这三种，假设分别有 $S_0,S_1,S_2$ 条。

由于已经缩过路径，所以 $0\to B,A\to 0$ 想要成环，只能借助 $0\to 0$ 边，因此我们可以先让 $0\to B,A\to 0$ 在内部先分别成环，然后最后再用 $0\to 0$ 去拼接 $0\to B,A\to 0$（以及 $A\to B$ ）。

也就是说我们要计算 $F_i(G_i)$ 表示 $0\to B(0\to A)$ 在内部组成恰好 $i$ 个环的方案数，直接算很难算，我们可以考虑广义容斥，先求出 $f_i$ 表示至少 $i$ 个环的方案数，然后容斥求出 $F$（ $G$ 同理）：

$$ f_i=\sum_{j=i}^{S_1}{S_1\choose j}s(j,i)(S_0+S_1-j)^{\underline{S_1-j}} $$

其中 $s(n,m)$ 为第一类斯特林数，即先钦点 $j$ 条 $0\to B$ 出来组成 $i$ 个环，方案数为 $s(j,i)$ ，剩下的 $n-j$ 条边可以成自环，也可以连向另外的 $0\to B$ ，还可以连向 $0\to 0$ ，反正需要找到一个地方接上去。

由于 $F,G$ 各自成环互不相干，所以可以直接 $F*G$ 得到 $i$ 个环的方案数。此时还剩下一些 $0\to B,A\to 0,A\to B$ 的边，我们可以用 $0\to 0$ 将他们连起来，感性理解一下（我不会证明QAQ），决定这些边成环数量的是 $0\to 0$ 的成环数量，而 $S_0$ 条 $0\to 0$ 成 $i$ 个环的方案数就是 $s(S_0,i)S_0!$ ，所以再用这个卷上 $F*G$ ，就可以得到答案了。

示例程序

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=2000,MOD=998244353;

int n,a[maxn+5],b[maxn+5],S[3],son[maxn+5],cir;bool vis[maxn+5];
int C[maxn+5][maxn+5],fac[maxn+5],A[maxn+5][maxn+5],s[maxn+5][maxn+5];
int f[maxn+5],g[maxn+5],F[maxn+5],G[maxn+5],H[maxn+5],tem[maxn+5],ans[maxn+5];

inline void Make(int n){
    fac[0]=1;for (int i=1;i<=n;i++) fac[i]=(LL)fac[i-1]*i%MOD;
    for (int i=s[0][0]=C[0][0]=A[0][0]=1;i<=n;i++)
        for (int j=C[i][0]=A[i][0]=1;j<=i;j++){
            s[i][j]=(s[i-1][j-1]+(LL)s[i-1][j]*(i-1)%MOD)%MOD;
            C[i][j]=(C[i-1][j-1]+C[i-1][j])%MOD;
            A[i][j]=(LL)C[i][j]*fac[j]%MOD;
        }
}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    scanf("%d",&n);Make(n);
    for (int i=1;i<=n;i++) scanf("%d",&a[i]);for (int i=1;i<=n;i++) scanf("%d",&b[i]);
    for (int i=1;i<=n;i++) son[i]=-1;for (int i=1;i<=n;i++) if (a[i]) son[a[i]]=b[i];
    for (int i=1;i<=n;i++)
        if (!a[i]){
            int x=b[i];while (x&&~son[x]) vis[x]=true,x=son[x];
            if (!x) S[0]++; else vis[x]=true,S[1]++;
        }
    for (int i=1;i<=n;i++)
        if (a[i]&&!vis[a[i]]){
            vis[a[i]]=true;int x=b[i];while (x&&~son[x]&&!vis[x]) vis[x]=true,x=son[x];
            if (!x) S[2]++; else if (x==a[i]) cir++; else vis[x]=true;
        }
    for (int i=0;i<=S[1];i++)
        for (int j=i;j<=S[1];j++)
            f[i]=(f[i]+(LL)C[S[1]][j]*s[j][i]%MOD*A[S[0]+S[1]-j][S[1]-j])%MOD;
    for (int i=0;i<=S[2];i++)
        for (int j=i;j<=S[2];j++)
            g[i]=(g[i]+(LL)C[S[2]][j]*s[j][i]%MOD*A[S[0]+S[2]-j][S[2]-j])%MOD;
    for (int i=0;i<=S[1];i++)
        for (int j=i;j<=S[1];j++)
            F[i]=(F[i]+(LL)(j-i&1?MOD-1:1)*C[j][i]%MOD*f[j]%MOD)%MOD;
    for (int i=0;i<=S[2];i++)
        for (int j=i;j<=S[2];j++)
            G[i]=(G[i]+(LL)(j-i&1?MOD-1:1)*C[j][i]%MOD*g[j]%MOD)%MOD;
    for (int i=0;i<=S[0];i++) H[i]=(LL)s[S[0]][i]*fac[S[0]]%MOD;
    for (int i=0;i<=n;i++)
        for (int j=0;i+j<=n;j++)
            tem[i+j]=(tem[i+j]+(LL)F[i]*G[j]%MOD)%MOD;
    for (int i=0;i<=n;i++)
        for (int j=0;i+j<=n;j++)
            ans[i+j]=(ans[i+j]+(LL)tem[i]*H[j]%MOD)%MOD;
    for (int i=0;i<n;i++) n-i-cir<0?putchar('0'):printf("%d",ans[n-i-cir]),i<n-1?putchar(' '):puts("");
    return 0;
}