題意

對于兩個排列 \(p,q\)，定義它們的距離為將 \(p\) 變成 \(q\) 的最小操作次數(shù)，其中每次操作可以交換 \(p\) 中兩個元素的位置。現(xiàn)在給定兩個長度為 \(n\) 的排列 \(p,q\)，其中一些位置被替換成了 \(0\)。對于每個 \(0\leq k\leq n-1\)，求補全 \(p,q\) 的方案數(shù)，使得兩者的距離恰好為 \(k\)。答案對 \(998244353\) 取模。\(1\leq n\leq 2\times 10^3\)。

題解

NOIP 模擬賽 T3。原題什么搞笑數(shù)據(jù)范圍。

先考慮 \(\forall i,p_i,q_i>0\) 怎么做，把排列看成置換，此時設(shè) \(p^{-1}q\) 中的置換環(huán)數(shù)為 \(C\)，則 \(p,q\) 的距離就是 \(n-C\)。從圖論角度考慮，這相當(dāng)于從 \(a_i\) 向 \(b_i\) 連單向邊，\(C\) 就是其中的環(huán)數(shù)。

回到原題，此時連的邊中有一些點是未確定的，我們把這些點設(shè)為 \(0\)。那么邊就有四類：一類邊 \((x,0)\)、二類邊 \((0,x)\)、三類邊 \((0,0)\)、四類邊 \((x,y)\)，其中 \(x,y>0\)。

顯然四類邊會構(gòu)成若干條鏈和環(huán)，我們把鏈全部縮成一個點，記錄環(huán)的個數(shù) \(cyc\)，最后再把 \(cyc\) 計入答案中。容易用并查集 \(\mathcal{O}(n\alpha(n))\) 維護這個過程。

然后如果存在一類邊 \((x,0)\) 和二類邊 \((0,y)\)，使得 \(x=y\)，那么我們把這兩條邊縮成一條三類邊。這樣子一、二類邊就不存在相同端點了。

接下來要計數(shù)的是，剩下來的三類邊連成若干個環(huán)的方案數(shù)。考察單個環(huán)中邊的構(gòu)成，我們觀察到其中要么全部是一類邊，要么全部是二類邊，要么全是三類邊，要么同時有一、二、三類邊，且一條二類邊 \((0,x)\) 和一條一類邊 \((y,0)\) 之間一定有三類邊間隔開來。

下面設(shè)一、二、三類邊分別有 \(c_1,c_2,c_3\) 條。

我們重點考察一個同時有一、二、三類邊的環(huán)。對于每條一類邊，它前面只能是一條一類邊或三類邊，對于每條二類邊，它后面只能是一條二類邊或三類邊。

注意到一條一類邊和它前面的三類邊縮在一起還是一條三類邊，二類邊同理，于是考察這樣的過程：我們先把所有 \(c_3\) 條三類邊鋪開，然后插入若干條一類邊，再把每條一類邊和它前面的邊縮在一起，這樣還是剩下 \(c_3\) 條三類邊，然后再同理插入若干條二類邊，最后把這些鋪開的三類邊連成若干個環(huán)。也就是說，最終每條三類邊，實際上依次由若干二類邊、一條原來的三類邊、若干一類邊構(gòu)成。這個結(jié)構(gòu)就很利于我們計數(shù)了。

我們先考察所有一類邊。設(shè) \(f_i\) 表示考慮所有一類邊，連出了 \(i\) 個只包含一類邊的環(huán)的方案數(shù)。枚舉這 \(i\) 個環(huán)用了 \(j\) 條邊，剩下的 \(c_1-j\) 條邊依次插入到三類邊中，每條邊可以接到一條一類邊或三類邊后面。可以列出式子：

可以同理求出 \(g_i\) 表示考慮所有二類邊，連出了 \(i\) 個只包含二類邊的環(huán)的方案數(shù)。

注意特判 \(c_3=0\) 的情況，此時 \(f_i=\displaystyle{c_1\brack i}\)，\(g_i=\displaystyle{c_2\brack i}\)。

再令 \(h_i\) 表示將所有三類邊連成 \(i\) 個環(huán)的方案數(shù)，我們在這里乘上給 \(0\) 填數(shù)的方案數(shù)。考察前面縮邊的過程，我們只需要確定 \(c_3\) 個 \(0\) 即可確定原來所有的 \(0\)，于是 \(h_i=\displaystyle{c_3\brack i}c_3!\)。

最后我們發(fā)現(xiàn)只需要把 \(f,g,h\) 依次卷起來即可得到答案。時間復(fù)雜度 \(\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;
}