Description：

给定两个排列 $p,q$ ，但是其中有些位置未知。补全两个排列，定义两个排列 $p,q$ 之间的距离为每次选择 $p$ 中两个元素交换，使其变成 $q$ 的最小次数。对于 $i \in [0,n-1]$ 求出补全后相似度为 $i$ 的方案数。

$1\leqslant n\leqslant 250$

Solution：

首先假设排列没有未知元素，那么两个排列都可以看成一个置换，要求的实际上就是 $n-$ 这两个置换的和的环的个数，因为最终一定是沿着环交换，转化成图论就是连边 $p_i\to q_i$ ，求图中环的个数，那么我们先把已知的构造出来，对于一整个环，我们可以答案 $+1$ 直接删掉，记这个的个数为 $cyc$ ，然后就是链的情况，发现我们实际上只要知道链的两个端点就可以了，链之间的点不会产生影响，那么我们可以按两端的情况分成 $x\to ?,?\to x,?\to ?$ 三种可能先一遍 $dfs$ 算出他们的个数分别为 $cnt1,cnt2,cnt4$ ， $m=cnt1+cnt2+cnt4$ ，然后就可以列答案的式子了： $$ f_x=\sum_{o_1=0}^x\sum_{k_1=o_1}^{cnt_1}\sum_{o_2=0}^{x-o_1}\sum_{k_2=o_2}^{cnt_2} C^{cnt_1}_{k_1}S_1(k_1,o_1)C^{cnt_2}_{k_2}S_1(k_2,o_2) P^{cnt_1-k_1+cnt_4-1}_{cnt_1-k_1}P^{cnt_2-k_2+cnt_4}_{cnt_2-k_2}S_1(cnt_4,x-o_1-o_2)cnt4! $$ $f_k$ 表示有 $k$ 个环的方案数，然后先枚举只用 $x\to ?$ 组成的环的个数 $o_1$ ，所用的个数 $k_1$ ，然后再枚举只用 $?\to x$ 组成的环的个数 $o_2$ 和所用的个数 $k_2$ ，因为如果这两个放在一起组成环，那么中间一定夹着 $?\to?$ 这样的链，所以我们把环按是否有 $?\to?$ 分类讨论，然后那两种链和 $?\to ?$ 组合可以看成是把某条链接在 $?\to?$ 的一边，形成一个更大的 $?\to?$ 链，那两种链一定分别接在 $?\to?$ 链的两侧所以互不影响。然后发现还是可以把两种链分别考虑，一个的方案数就是把 $x\to?/?\to x$ 和 $?\to?$ 排序的方案数，也就是类似球相同桶不同可以空的计算方法，但是球也是不同的，所以是一个排列数，显然是 $P^{cnt_1-k_1+cnt_4}_{cnt_1-k_1}$ ，而且桶还要乘上一个 $cnt_4!$ 因为互换之后是另一种方案，这样最后还相当于是 $cnt4$ 个 $?\to?$ 的链，他们应该排成 $x-o_1-o_2$ 个轮换，所以方案数就是第一类斯特林数了。

先设： $$ a[i]=\sum_{k_1=i}^{cnt_1}C^{cnt_1}_{k_1}S_1(k_1,i)P^{cnt_1-k_1+cnt_4-1}_{cnt_1-k_1}\\ b[i]=\sum_{k_2=i}^{cnt_2}C^{cnt_2}_{k_2}S_1(k_2,i)P^{cnt_2-k_2+cnt_4-1}_{cnt_2-k_2}\\ $$ 这两个可以 $O(n^2)$ 求 $$ c[x]=\sum_{i=0}^xa[i]b[x-i] $$ 这个也可以 $O(n^2)$ 求 $$ f[x]=\sum_{i=0}^xc[i]S_1(cnt_4,x-i)cnt4! $$ 也是 $O(n^2)$ 求。

复杂度主要就是在求 $a[i]$ 和 $b[i]$ 的时候，别的都可以优化。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n;

#define MAXN 510

#define MOD 998244353

int p[MAXN],q[MAXN];

bool vis[MAXN];

int nxt[MAXN];

int ind[MAXN];

int cnt1 = 0,cnt2 = 0,cnt3 = 0,cnt4 = 0;

void dfs(int k,int rt)

{

	vis[k] = true;

	if(nxt[k] != 0)

	{

		if(!vis[nxt[k]])dfs(nxt[k],rt);

		else ++cnt3;

	}

	else

	{

		if(rt > n && k > n)++cnt4;

		else if(rt <= n && k > n)++cnt1;

		else if(rt > n && k <= n)++cnt2;

	}

	return;

}

int P[MAXN][MAXN],C[MAXN][MAXN],S[MAXN][MAXN];

void init()

{

	S[0][0] = P[0][0] = C[0][0] = 1;

	for(int i = 1;i <= n;++i)

	{

		C[i][0] = P[i][0] = 1;

		for(int j = 1;j <= i;++j)

		{

			C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % MOD;

			P[i][j] = (1ll * j * P[i - 1][j - 1] + P[i - 1][j]) % MOD;

			S[i][j] = (1ll * (i - 1) * S[i - 1][j] + S[i - 1][j - 1]) % MOD;

		}

	}

	return;

}

int a[MAXN],b[MAXN],c[MAXN],f[MAXN];

int main()

{

	scanf("%d",&n);

	for(int i = 1;i <= n;++i)scanf("%d",&p[i]);

	for(int i = 1;i <= n;++i)scanf("%d",&q[i]);

	for(int i = 1;i <= (n << 1);++i)vis[i] = true;

	for(int i = 1;i <= n;++i)

	{

		int x = (p[i] ? p[i] : i + n);

		int y = (q[i] ? q[i] : i + n);

		vis[x] = vis[y] = false;

		if(x <= n || y <= n)

		{

			nxt[x] = y;

			++ind[y];

		}

	}

	for(int i = 1;i <= (n << 1);++i)

	{

		if(!vis[i] && ind[i] == 0)dfs(i,i);

	}

	for(int i = 1;i <= (n << 1);++i)

	{

		if(!vis[i])dfs(i,i);

	}

	init();

	if(cnt4)

	{

		for(int i = 0;i <= cnt1;++i)

		{

			for(int k = i;k <= cnt1;++k)

			{

				a[i] = (a[i] + 1ll * C[cnt1][k] * S[k][i] % MOD * P[cnt1 - k + cnt4 - 1][cnt1 - k] % MOD) % MOD;

			}

		}

		for(int i = 0;i <= cnt2;++i)

		{

			for(int k = i;k <= cnt2;++k)

			{

				b[i] = (b[i] + 1ll * C[cnt2][k] * S[k][i] % MOD * P[cnt2 - k + cnt4 - 1][cnt2 - k] % MOD) % MOD;

			}

		}

	}

	else

	{

		for(int i = 0;i <= cnt1;++i)a[i] = S[cnt1][i];

		for(int i = 0;i <= cnt2;++i)b[i] = S[cnt2][i];

	}

	//for(int i = 0;i <= cnt1;++i)cout << a[i] << " ";cout << endl;

	//for(int i = 0;i <= cnt2;++i)cout << b[i] << " ";cout << endl;

	for(int i = 0;i <= n;++i)

	{

		for(int j = 0;j <= i;++j)

		{

			c[i] = (c[i] + 1ll * a[j] * b[i - j]) % MOD;

		}//cout << c[i] << " ";

	}//cout << endl;

	for(int i = 0;i <= n;++i)

	{

		for(int j = 0;j <= i;++j)

		{

			f[i] = (f[i] + 1ll * c[j] * S[cnt4][i - j]) % MOD;

		}

	}

	int fac = 1;

	for(int i = 1;i <= cnt4;++i)fac = 1ll * fac * i % MOD; 

	for(int i = 0;i < n;++i)

	{

		if(n - i - cnt3 < 0)printf("0 ");

		else printf("%d ",1ll * f[n - i - cnt3] * fac % MOD);

	}

	puts("");

	return 0;

}