[CodeForces 715E] Complete the Permutations [BZOJ 5406] Gift【计数】【第一类斯特林数】

Description

Solution

PS：卷积分明可以暴力做，不明白为什么codeforces上打了个FFT的标签

Code

#include <bits/stdc++.h>
#define fo(i,a,b) for(int i=a;i<=b;++i)
#define fod(i,a,b) for(int i=a;i>=b;--i)
#define N 2005
#define LL long long
#define mo 998244353
using namespace std;
LL s1[N][N],a,b,c,d,js[N],ny[N],f[N],g[N],h[N];
int n,m,pt[N],a1[N],b1[N],nt[N],rd[N];
bool bz[N],bp[N];
LL ksm(LL k,LL n)
{
	LL s=1;
	for(;n;n>>=1,k=k*k%mo) if(n&1) s=s*k%mo;
	return s;
}
void dfs(int k)
{
	if(!k) return;
	bp[k]=1;
	bz[k]=1;
	if(nt[k]!=k)
	{
		if(bp[nt[k]]) d++;
		else dfs(nt[k]),nt[k]=nt[nt[k]];
	}
	bp[k]=0;
}
LL C(int n,int m)
{
	if(n<m) return 0;
	return js[n]*ny[m]%mo*ny[n-m]%mo;
}
int main()
{
	cin>>n;
	js[0]=1;
	fo(i,1,2000) js[i]=js[i-1]*(LL)i%mo;
	ny[2000]=ksm(js[2000],mo-2);
	fod(i,1999,0) ny[i]=ny[i+1]*(LL)(i+1)%mo;
	s1[0][0]=1;
	fo(i,1,n)
	{
		s1[i][0]=0;
		fo(j,1,i) s1[i][j]=(s1[i-1][j-1]+s1[i-1][j]*(LL)(i-1)%mo)%mo; 
	}
	fo(i,1,n) scanf("%d",&a1[i]),nt[i]=i;
	fo(i,1,n)
	{
		scanf("%d",&b1[i]);
		if(b1[i]) 
		{
			nt[b1[i]]=a1[i];
			if(a1[i]==b1[i]) d++,bz[a1[i]]=1;
		}
		if(a1[i]) rd[a1[i]]++;
	}
	fo(i,1,n) if(!bz[i]) dfs(i);
	fo(i,1,n)
	{
		if(!b1[i]) 
		{
			if(nt[a1[i]]==0) a++;
			else b++;
		} 
		else if(rd[b1[i]]==0&&nt[a1[i]]==0) c++;
	}
	fo(i,0,b)
	{
		fo(j,i,b)
		{
			LL v=0;
			if(a>0) v=js[a+b-j-1]*ny[a-1]%mo;
			else if(j==b) v=1;
			f[i]=(f[i]+C(b,j)*s1[j][i]%mo*v%mo)%mo;
		}
	}
	fo(i,0,c)
	{
		fo(j,i,c)
		{
			LL v=0;
			if(a>0) v=js[a+c-j-1]*ny[a-1]%mo;
			else if(j==c) v=1;
			g[i]=(g[i]+C(c,j)*s1[j][i]%mo*v%mo)%mo;
		}
	}
	fo(i,0,a) h[i]=s1[a][i]*js[a]%mo;
	fod(i,n,0) 
	{
		LL v=0;
		fo(j,0,i) v=(v+h[i-j]*g[j]%mo)%mo;
		h[i]=v;
	}
	fod(i,n,0)
	{
		LL v=0;
		fo(j,0,i) v=(v+h[i-j]*f[j]%mo)%mo;
		f[i]=v;
	}
	fo(i,0,n-1)
	{
		if(n-i-d<0) printf("0 ");
		else printf("%lld ",f[n-(i+d)]);
	}
}