题意
对于两个排列 \(p,q\)，定义它们的距离为将 \(p\) 变成 \(q\) 的最小操作次数，其中每次操作可以交换 \(p\) 中两个元素的位置。现在给定两个长度为 \(n\) 的排列 \(p,q\)，其中一些位置被替换成了 \(0\)。对于每个 \(0\leq k\leq n-1\)，求补全 \(p,q\) 的方案数，使得两者的距离恰好为 \(k\)。答案对 \(998244353\) 取模。\(1\leq n\leq 2\times 10^3\)。
题解
NOIP 模拟赛 T3。原题什么搞笑数据范围。
先考虑 \(\forall i,p_i,q_i>0\) 怎么做，把排列看成置换，此时设 \(p^{-1}q\) 中的置换环数为 \(C\)，则 \(p,q\) 的距离就是 \(n-C\)。从图论角度考虑，这相当于从 \(a_i\) 向 \(b_i\) 连单向边，\(C\) 就是其中的环数。
回到原题，此时连的边中有一些点是未确定的，我们把这些点设为 \(0\)。那么边就有四类：一类边 \((x,0)\)、二类边 \((0,x)\)、三类边 \((0,0)\)、四类边 \((x,y)\)，其中 \(x,y>0\)。
显然四类边会构成若干条链和环，我们把链全部缩成一个点，记录环的个数 \(cyc\)，最后再把 \(cyc\) 计入答案中。容易用并查集 \(\mathcal{O}(n\alpha(n))\) 维护这个过程。
然后如果存在一类边 \((x,0)\) 和二类边 \((0,y)\)，使得 \(x=y\)，那么我们把这两条边缩成一条三类边。这样子一、二类边就不存在相同端点了。
接下来要计数的是，剩下来的三类边连成若干个环的方案数。考察单个环中边的构成，我们观察到其中要么全部是一类边，要么全部是二类边，要么全是三类边，要么同时有一、二、三类边，且一条二类边 \((0,x)\) 和一条一类边 \((y,0)\) 之间一定有三类边间隔开来。
下面设一、二、三类边分别有 \(c_1,c_2,c_3\) 条。
我们重点考察一个同时有一、二、三类边的环。对于每条一类边，它前面只能是一条一类边或三类边，对于每条二类边，它后面只能是一条二类边或三类边。
注意到一条一类边和它前面的三类边缩在一起还是一条三类边，二类边同理，于是考察这样的过程：我们先把所有 \(c_3\) 条三类边铺开，然后插入若干条一类边，再把每条一类边和它前面的边缩在一起，这样还是剩下 \(c_3\) 条三类边，然后再同理插入若干条二类边，最后把这些铺开的三类边连成若干个环。也就是说，最终每条三类边，实际上依次由若干二类边、一条原来的三类边、若干一类边构成。这个结构就很利于我们计数了。
我们先考察所有一类边。设 \(f_i\) 表示考虑所有一类边，连出了 \(i\) 个只包含一类边的环的方案数。枚举这 \(i\) 个环用了 \(j\) 条边，剩下的 \(c_1-j\) 条边依次插入到三类边中，每条边可以接到一条一类边或三类边后面。可以列出式子：
可以同理求出 \(g_i\) 表示考虑所有二类边，连出了 \(i\) 个只包含二类边的环的方案数。
注意特判 \(c_3=0\) 的情况，此时 \(f_i=\displaystyle{c_1\brack i}\)，\(g_i=\displaystyle{c_2\brack i}\)。
再令 \(h_i\) 表示将所有三类边连成 \(i\) 个环的方案数，我们在这里乘上给 \(0\) 填数的方案数。考察前面缩边的过程，我们只需要确定 \(c_3\) 个 \(0\) 即可确定原来所有的 \(0\)，于是 \(h_i=\displaystyle{c_3\brack i}c_3!\)。
最后我们发现只需要把 \(f,g,h\) 依次卷起来即可得到答案。时间复杂度 \(\mathcal{O}(n^2)\)。
代码
#include <bits/stdc++.h>using namespace std;#define lowbit(x) ((x) & -(x))
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
const int N = 2e3 + 5, MOD = 998244353;template<typename T> inline void chk_min(T &x, T y) { x = min(x, y); }
template<typename T> inline void chk_max(T &x, T y) { x = max(x, y); }
inline int add(int x, int y) { return x += y, x >= MOD ? x - MOD : x; }
inline int sub(int x, int y) { return x -= y, x < 0 ? x + MOD : x; }
inline void cadd(int &x, int y) { x += y, x < MOD || (x -= MOD); }
inline void csub(int &x, int y) { x -= y, x < 0 && (x += MOD); }int n, c1, c2, c3, cyc, a[N], b[N], cnt[N], f[N], g[N], h[N], tmp[N], ans[N];
int fac[N], ifac[N], S[N][N];struct DSU {int fa[N], sz[N];inline void init() { for (int i = 1; i <= n; ++i) fa[i] = i, sz[i] = 1; }inline int find(int x) { return x == fa[x] ? x : fa[x] = find(fa[x]); }inline void unite(int x, int y) {x = find(x), y = find(y);if (x == y) return ++cyc, void();if (sz[x] > sz[y]) swap(x, y);fa[x] = y, sz[y] += sz[x];}
} dsu;inline int qpow(int a, int b) {int res = 1;for (; b; b >>= 1) {if (b & 1) res = (ll)res * a % MOD;a = (ll)a * a % MOD;}return res;
}
inline void prework(int n) {fac[0] = 1;for (int i = 1; i <= n; ++i) fac[i] = (ll)fac[i - 1] * i % MOD;ifac[n] = qpow(fac[n], MOD - 2);for (int i = n - 1; ~i; --i) ifac[i] = (ll)ifac[i + 1] * (i + 1) % MOD;S[0][0] = 1;for (int i = 1; i <= n; ++i) for (int j = 1; j <= n; ++j) S[i][j] = add(S[i - 1][j - 1], (ll)S[i - 1][j] * (i - 1) % MOD);
}
inline int C(int n, int m) {if (n < 0 || m < 0 || n < m) return 0;return (ll)fac[n] * ifac[m] % MOD * ifac[n - m] % MOD;
}int main() {ios::sync_with_stdio(0), cin.tie(0);cin >> n, dsu.init(), prework(n);for (int i = 1; i <= n; ++i) cin >> a[i];for (int i = 1; i <= n; ++i) {cin >> b[i];if (a[i] && b[i]) dsu.unite(a[i], b[i]);}for (int i = 1; i <= n; ++i) {if (a[i] && b[i]) continue;if (a[i]) ++c1, ++cnt[dsu.find(a[i])];else if (b[i]) ++c2, ++cnt[dsu.find(b[i])];else ++c3;}for (int i = 1; i <= n; ++i) if (cnt[i] == 2) --c1, --c2, ++c3;if (!c3) {for (int i = 0; i <= c1; ++i) f[i] = S[c1][i];for (int i = 0; i <= c2; ++i) g[i] = S[c2][i];} else {for (int i = 0; i <= c1; ++i) for (int j = i; j <= c1; ++j)cadd(f[i], (ll)C(c1, j) * S[j][i] % MOD * C(c1 - j + c3 - 1, c3 - 1) % MOD * fac[c1 - j] % MOD);for (int i = 0; i <= c2; ++i) for (int j = i; j <= c2; ++j)cadd(g[i], (ll)C(c2, j) * S[j][i] % MOD * C(c2 - j + c3 - 1, c3 - 1) % MOD * fac[c2 - j] % MOD);}for (int i = 0; i <= c3; ++i) h[i] = (ll)S[c3][i] * fac[c3] % MOD;for (int i = 0; i <= c1; ++i) for (int j = 0; j <= c2; ++j) cadd(tmp[i + j], (ll)f[i] * g[j] % MOD);for (int i = 0; i <= c1 + c2; ++i) for (int j = 0; j <= c3; ++j) cadd(ans[i + j + cyc], (ll)tmp[i] * h[j] % MOD);for (int i = 0; i < n; ++i) cout << ans[n - i] << ' ';return 0;
}