[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)]);
}
}