给出两个排列(p,q)，其中有些位置不确定。
定义(p,q)的距离为(p)进行最少多少次交换操作之后可以得到(q)。
问所有的合法方案下距离为(k)（(k=0dots n-1)）的方案数。
(nle 250)（实际上可以做(nle 5000)）
官方题解不知道在搞什么，时间复杂度是(O(n^3lg n))（用NTT）或(O(n^{3.58}))（用叫Karatsuba的快速乘法）。
下面是(O(n^2))的阳间做法：
假如(p,q)已经确定，(p)到(q)的距离：建图，连边(p_i,q_i)，距离为(n-轮换数)。
现在分析一下图中四种边（由于只关心头尾，所以链可以视作边）：((0,x),(x,0),(0,0),(x,y))。如果出现((x,y))就把(x,y)缩点并把这条边去掉，如果存在((x_1,0))和((0,x_2))且(x_1=x_2)，把这两条边去掉并换成((0,0))。这样处理过后同一个(x)只会出现在一条边中。记最终剩下的三种边分别为一二三类边，个数分别为(a,b,c)。（稍微注意还要处理一下本来就存在的环）
考虑这些边连上之后环的组成。发现：
- 都是一类边，或都是二类边。（下文分别称其为一类环、二类环）
- 一类边和二类边都有，其中一类边到二类边中间有三类边连接。
分别先只考虑一类边和二类边。设(F_i)为此时恰好有(i)个一类环的方案数，设(f_i)为至少，算出(f)反演可得(F)。则有：
其中(s)表示斯特林数。
意义：枚举(j)条一类边组成(x)个环，剩下的(a-j)条边都需要接后继，((0,x))后面可以接((0,x))或((0,0))。
同理可以求出(G_i)表示恰好有(i)个二类环的方案数。
接下来考虑杂环的组成成分：可以发现，在计算一类边的拼接操作时，如果有((0,x))后面接((0,0))，可以视作两者合并成((0,0))；二类边同理。所以可以视作：拼完了一类环和二类环，剩下的杂环全部由三类边组成，三类边还是(c)个（其实在前面，可以视作先拼一类边再拼二类边，由于拼二类边的时候三类边个数还是(c)，所以并没有发生矛盾）。
设(H_i=s(c,i))。于是((F*G*H)_i)为恰好有(i)个环的方案数的生成函数。
时间(O(n^2))。
using namespace std;
#include <bits/stdc++.h>
#define N 2505
#define ll long long
#define mo 998244353
ll qpow(ll x,ll y=mo-2){
ll r=1;
for (;y;y>>=1,x=x*x%mo)
if (y&1)
r=r*x%mo;
return r;
}
int n;
int p[N],q[N];
ll fac[N],ifac[N];
ll s[N][N];
void initCs(){
fac[0]=1;
for (int i=1;i<=n;++i)
fac[i]=fac[i-1]*i%mo;
ifac[n]=qpow(fac[n]);
for (int i=n-1;i>=0;--i)
ifac[i]=ifac[i+1]*(i+1)%mo;
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]+(i-1)*s[i-1][j])%mo;
}
ll C(int m,int n){return fac[m]*ifac[n]%mo*ifac[m-n]%mo;}
int a,b,c,o;
int dsu[N];
int getdsu(int x){return dsu[x]==x?x:dsu[x]=getdsu(dsu[x]);}
void initabc(){
for (int i=1;i<=n;++i)
dsu[i]=i;
for (int i=1;i<=n;++i){
int u=getdsu(p[i]),v=getdsu(q[i]);
if (u && v)
o+=(dsu[u]==dsu[v]),dsu[u]=v;
}
static int bz[N];
for (int i=1;i<=n;++i){
int u=getdsu(p[i]),v=getdsu(q[i]);
if (!u && !v)
c++;
else if (!u && v){
if (bz[v]==1)
c++,b--;
else
bz[v]=-1,a++;
}
else if (u && !v){
if (bz[u]==-1)
c++,a--;
else
bz[u]=1,b++;
}
}
}
int f[N],g[N],h[N],pro[N];
void rev(int a,int f[]){
static int F[N];
for (int i=0;i<=a;++i){
ll sum=0;
for (int j=i;j<=a;++j)
(sum+=f[j]*C(j,i)*(j-i&1?-1:1))%=mo;
F[i]=(sum+mo)%mo;
}
memcpy(f,F,sizeof(int)*(a+1));
}
void calcfg(int a,int f[]){
for (int i=0;i<=a;++i){
ll sum=0;
for (int j=i;j<=a;++j)
(sum+=C(a,j)*s[j][i]%mo*fac[a-j+c]%mo*ifac[c])%=mo;
f[i]=sum;
}
rev(a,f);
}
void multi(int c[],int a[],int b[]){
static int t[N];
for (int i=0;i<=n;++i){
ll sum=0;
for (int j=0;j<=i;++j)
sum=(sum+(ll)a[j]*b[i-j])%mo;
t[i]=sum;
}
memcpy(c,t,sizeof(int)*(n+1));
}
int main(){
// freopen("in.txt","r",stdin);
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]);
initCs();
initabc();
calcfg(a,f);
calcfg(b,g);
for (int i=0;i<=c;++i)
h[i]=s[c][i];
multi(pro,f,g);
multi(pro,pro,h);
for (int i=0;i<n;++i)
printf("%d ",(n-o-i>=0?pro[n-o-i]:0)*fac[c]%mo);
return 0;
}