CF715E Complete the Permutations

Description

给定两个 $1\sim n$ 的排列 $p$ 和 $q$ ，其中有些位置未知，用 $0$ 表示。
定义两个排列之间的相似度是：每次从 $p$ 中选择两个元素交换，使其变成 $q$ 的最小次数。
现在要求不全这两个序列，求出对于 $i\in [0,n-1]$ ，补全后相似度为 $i$ 的方案数。
$n\leq 300$

Solution

这道题好神啊。

先考虑怎么计算两个完全排列之间的相似度。因为交换不限于两个相邻的数之间，所以如果把 $p\rightarrow q$ 视作置换，对于每一个置换环，代价都是环长 $-1$ 。所以，我们让 $p_i$ 向 $q_i$ 连边，那么在最后的图中如果有 $m$ 个环，相似度就是 $n-m$ 。

现在加上 $0$ 的限制。我们从最简单的考虑：如果两个序列全都是 $0$ 怎么办。显然 $p$ 序列的任意一种填法对答案的贡献都是一样的，所以我们钦定 $p_i=i$ ，再限定 $q_i$ 的填法，最后给答案乘上 $n!$ 即可。考虑最后的图，可知每个点一定是一个前驱节点、一个后继节点——也就是每个点一定在一个简单环中。当环的数量为 $m$ 时，方案数为 $\begin{bmatrix}n\\m\end{bmatrix}$。并且这个方案与填 $q_i$ 的方案是一一对应的。

现在某些位置提前钦定了一些数。我们还是考虑连出来的图。这张图一定由 $4$ 部分组成：

• 数和数形成的链 / 环。
• 起点为数，终点为 $0$ 的链。假设数为 $x$ ，那么如果存在这样的链，$x$ 一定不在 $q$ 中出现， $0$ 一定在 $q$ 中。
• 起点为 $0$ ，终点为数的链。假设数为 $x$ ，那么如果存在这样的链，$x$ 一定不在 $p$ 中出现， $0$ 一定在 $p$ 中。
• 起点为 $0$ ，终点为 $0$ 的链。

注意这里的 $0$ 不是指一个节点，而是泛称空的位置。

对于第一种情况，我们管不着，也不用管。

对于第二种情况，我们考虑最后的这种链在图中如何存在。首先，第二种链和第二种链可以成环，并且 $n$ 条第二种链成的环可以看成是 $n$ 个起点的环排列。其次，第二种链和第四种链也可以合并成第四种链，只要在某个第四种链的结束位置填上该第二种链的起始位置的数即可。注意我们这样操作以后第四种链的数目不变。

考虑第二种链和第三种链之间的关系。第二种链内部成环与第三种链没有影响；第二种链与第四种链合并时，只需要结束位置，而第三种链显然只需要开头位置，这里也是独立的；第二种链如果要与第三种链串在一个环中，必然要借助第四种链，考虑这种情况时，我们可以先考虑将第二/三种链分别与第四种链串起来，这个时候的方案数就只与第四种链的成环方案数有关了。

所以我们在考虑第二种链的时候，我们只需要考虑第二种链内部成 $x$ 个环，剩下的链都与第四种链合并的方案数即可。问题转化为怎么求第二种链内部恰好成 $x$ 个环的方案数。我们可以算出成至少 $x$ 个环的方案数（设有 $m$ 条第二种链，$k$ 条第四种链）：

$f_x=\sum_{i=0}^{m}\binom{m}{i}\begin{bmatrix}i\\x\end{bmatrix}(k+m-i)^{\underline{m-i}}$

然后二项式反演就可以转化为恰好。第三种链同理。然后这两部分是完全独立的，我们直接分别求完以后背包合并就可以得到第二/三种链恰好得到 $x$ 个环的方案数。

第二/三种链与第四种链合并不改变第四种链的数量。现在的问题就是第四种链成 $x$ 个环的方案如何统计。目前的图中，只存在数到数的链、数到数的环和 $0$ 到 $0$ 的链。假设 $0$ 到 $0$ 的链有 $z$ 条。
那么实际上相当于 $p$ 和 $q$ 中各有 $z$ 个数未确定。这 $z$ 个数不一定完全相同，但是我们不要忘记了数到数的链。一个仅在 $p$ 中出现而未在 $q$ 中出现的数 $x$ 一定会最终指向一个仅在 $q$ 中出现而未在 $p$ 中出现的数 $y$ ，这条链中间的点都没有用可以缩掉，那么相当于是一个 $x\rightarrow y$ 的映射。所以这 $z$ 个数是本质上一定是相同的。 故直接考虑把这 $z$ 个数分成圆排列的方案数就行了。

背包合并第二/三种链和第四种链，就可以得到整张图去掉已经有的环后恰好得到 $x$ 个环的方案数。

考虑到整个过程中我们都没有考虑第四种链的先后顺序，而第四种链在最终图中是有序的，所以答案再乘上一个阶乘。

复杂度 $\mathcal{O}(n^2)$ 。

Code

const int N = 6e2 + 5, mod = 998244353;
using namespace std;
int n, sum, ori, cnta, cntb;
int a[N], b[N], to[N], vis[N], deg[N];
long long f[N], g[N], h[N], s[N][N], fac[N], inv[N], invf[N];
int binom(int n, int m){
    if(n < 0 or m < 0 or n - m < 0) return 0;
    return fac[n] * invf[m] % mod * invf[n - m] % mod;
}
void calc(long long *f, int cnt){
    for(int i = 0; i <= cnt; ++i) f[i] = 0;
    for(int i = 0; i <= cnt; ++i)
    for(int j = i; j <= cnt; ++j){
        int now = s[j][i] * fac[cnt - j + sum] % mod * invf[sum] % mod * binom(cnt, j) % mod;
        (f[i] += now) %= mod;
    }
    for(int i = 0; i <= cnt; ++i){
        int v = 0;
        for(int j = i; j <= cnt; ++j)
            if(j - i & 1) v = (v + mod - f[j] * binom(j, i) % mod) % mod;
            else v = (v + f[j] * binom(j, i) % mod) % mod;
        f[i] = v;
    }
}
int Find(int x){return x == f[x] ? x : f[x] = Find(f[x]);}
void Link(int x, int y){
    x = Find(x), y = Find(y);
    if(x == y) return ++ori, void();
    f[x] = y;
}
void dfs0(int p){
    if(p <= n) vis[p] = 1;
    if(!to[p])
        ++(p <= n ? cntb : sum);
    else dfs0(to[p]);
}
void dfs1(int p){
    if(p > n)  ++cnta;
    else if(to[p]) vis[p] = 1, dfs1(to[p]);
}
void dfs2(int p){
    if(vis[p]) ++ori;
    else vis[p] = 1, dfs2(to[p]);
}
int main(){

    ios::sync_with_stdio(false);

    cin >> n;
    for(int i = 1; i <= n; ++i) cin >> a[i];
    for(int i = 1; i <= n; ++i) cin >> b[i];
    for(int i = 1; i <= n; ++i)
        if(a[i] or b[i])
            if(a[i] and b[i]) to[a[i]] = b[i], deg[b[i]] = 1;
            else if(a[i]) to[a[i]] = i + n;
                 else to[i + n] = b[i]; 
        else ++sum;
    for(int i = n + 1; i <= n + n; ++i)
        if(to[i]) dfs0(i);
    for(int i = 1; i <= n; ++i)
        if(to[i] and !vis[i] and !deg[i]) dfs1(i);
    for(int i = 1; i <= n; ++i)
        if(to[i] and !vis[i]) dfs2(i);

    fac[0] = fac[1] = inv[0] = inv[1] = invf[0] = invf[1] = 1;
    for(int i = 2; i <= n; ++i)
        fac[i] = 1ll * fac[i - 1] * i % mod,
        inv[i] = 1ll * (mod - mod / i) * inv[mod % i] % mod,
        invf[i] = 1ll * inv[i] * invf[i - 1] % mod;
    s[0][0] = 1; 
    for(int i = 1; i <= n; ++i)
    for(int j = 1; j <= i; ++j)
        s[i][j] = (s[i - 1][j - 1] + s[i - 1][j] * (i - 1) % mod) % mod;

    calc(f, cnta), calc(g, cntb);

    for(int i = 0; i <= cnta; ++i)
    for(int j = 0; j <= cntb; ++j)
        (h[i + j] += f[i] * g[j] % mod) %= mod;
    int cnt = cnta + cntb;
    memset(f, 0, sizeof f);
    for(int i = 0; i <= cnt; ++i)
    for(int j = 0; j <= sum; ++j)
        (f[i + j] += h[i] * s[sum][j] % mod) %= mod;

    for(int i = 0; i < n; ++i)
        cout << (n - i - ori >= 0 ? f[n - i - ori] * fac[sum] % mod : 0) << " ";
    return 0;
}