Codeforces 715E. Complete the Permutations(斯特林数+二项式反演+卷积)

题解

  这个题官方题解的做法非常麻烦,而且是O(n3logn)O(n^3logn)的,实际上这个题可以做到O(n2)O(n^2),从这个题解学来的QAQ
  首先这题显然两个排列就是个置换,答案显然就是nn-置换环的个数,那么我们要做的就是对每一个ii都求出构造nin-i个环的方案数。
  对于一些给定数字之间连边,如果形成了一条链,那么显然可以把除链头链尾之外的点删去,因为这样不会改变环数。如果给定数字形成了一个环,那么直接把这个环上所有数字删去,然后环数+1+1
  进行了以上操作之后,图里剩下的环点数不会超过33个,由一个??和两个给定数字组成。
  那么可以dfsdfsxx->????->xx,自环,??->??的方案数分别表示为cnt14cnt_{1\sim 4},然后来尝试构造环。
  因为只可能xx->??连向??->yy,所以如果这两种边在同一个环里并且相邻的话必须按一定顺序,因此我们不能直接用组合数算出这两种边成环的方案数,那怎么做呢
  先算出用cnt1cnt1的边自己成环的方案数,恰好ii个不好算,考虑算至少ii个的然后用二项式反演/容斥算出恰好ii个的,设FiF_i为至少ii个环的方案,则有:

Fk=i=kcnt1(cnt1i)[  i  k]Acnt1i+cnt4cnt1iF_k=\sum_{i=k}^{cnt_1}\binom{cnt_1}{i} \begin{bmatrix} \ \ i\ \ \\ k \end{bmatrix} A_{cnt1-i+cnt_4}^{cnt1-i}

  就是先搞出kk个环,剩下的边可以自己搞成环,也可以和??->??的相连,变成一条链,等会和??->??的方案卷起来变成环。
  cnt2cnt_2的边同理,然后把cnt1cnt_1的边和cnt2cnt_2的边卷起来,表示两种边自己组成的环互不影响,而两种边方案中的链相组合,两个边相邻那么必定选的是同一条??->??,所以可以直接当成按一定顺序的,满足了上方的要求,最后再和??->??自己组成环的方案卷起来,ii个环方案显然是s(cnt4,i)s(cnt_4,i),因为每个??->??上可以写的数字有cnt4cnt_4个,所以最后还要乘上cnt4!cnt_4!,然后就可以得到答案了。
  UPD:思考了一下总结出一个规律,两种物品的方案卷积得到的是互不影响的方案数,而要让他们互相影响,可以在算一种物品的方案时预先乘上与另一种物品有关的方案数,再卷积起来的时候就能让他们互相影响了。

代码

#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#define MOD(x) ((x)>=mod?(x)-mod:(x))
using namespace std;
const int maxn=510, inf=1e9, mod=998244353;
int n, cnt1, cnt2, cnt3, cnt4;
int a[maxn], b[maxn], f[maxn], g[maxn], ans1[maxn], ans[maxn], nxt[maxn], ru[maxn], G[maxn];
int A[maxn][maxn], C[maxn][maxn], s[maxn][maxn];
bool v[maxn];

template<typename T>
inline void read(T &k)
{
	int f=1; k=0; char c=getchar();
	while(c<'0' || c>'9') c=='-' && (f=-1), c=getchar();
	while(c<='9' && c>='0') k=k*10+c-'0', c=getchar();
	k*=f;
}

void dfs(int x, int fa)
{
	v[x]=1;
	if(nxt[x])
	{
		if(!v[nxt[x]]) dfs(nxt[x], fa);
		else cnt3++;
	}
	else
	{
		if(fa>n && x>n) cnt4++;
		else if(fa<=n && x>n) cnt1++;
		else if(fa>n && x<=n) cnt2++;
	}
}

inline void init()
{
	s[0][0]=C[0][0]=A[0][0]=1;
	for(int i=1;i<=n;i++) 
	{
		C[i][0]=A[i][0]=1;
		for(int j=1;j<=i;j++) 
		{
			C[i][j]=MOD(C[i-1][j-1]+C[i-1][j]);
			A[i][j]=(1ll*j*A[i-1][j-1]+A[i-1][j])%mod;
			s[i][j]=(1ll*(i-1)*s[i-1][j]+s[i-1][j-1])%mod;
		}
	}
}

inline void getans(int n, int *f)
{
	for(int i=0;i<=n;i++)
	{
		for(int j=i;j<=n;j++) 
		f[i]=(f[i]+1ll*C[n][j]*s[j][i]%mod*A[n-j+cnt4][n-j])%mod;
	}
	memset(G, 0, sizeof(G));
	for(int i=0;i<=n;i++)
	{
		for(int j=i, fz=1;j<=n;j++, fz=-fz)
		G[i]=(G[i]+1ll*C[j][i]*f[j]%mod*fz+mod)%mod;
	}
	memcpy(f, G, sizeof(G));
}

int main()
{
	read(n); for(int i=1;i<=(n<<1);i++) v[i]=1;
	for(int i=1;i<=n;i++) read(a[i]);
	for(int i=1;i<=n;i++) read(b[i]);
	for(int i=1;i<=n;i++)
	{
		int x=a[i]?a[i]:i+n, y=b[i]?b[i]:i+n;
		v[x]=v[y]=0;
		if(x<=n || y<=n) nxt[x]=y, ru[y]++;
	}
	for(int i=1;i<=(n<<1);i++) if(!v[i] && !ru[i]) dfs(i, i);
	for(int i=1;i<=(n<<1);i++) if(!v[i]) dfs(i, i);
	init(); getans(cnt1, f); getans(cnt2, g);
	for(int i=0;i<=n;i++) 
	{
		for(int j=0;j<=i;j++) 
		ans1[i]=(ans1[i]+1ll*f[j]*g[i-j])%mod;
	}
	for(int i=0;i<=n;i++)
	{
		for(int j=0;j<=i;j++)
		ans[i]=(ans[i]+1ll*ans1[j]*s[cnt4][i-j])%mod;
		ans[i]=1ll*ans[i]*A[cnt4][cnt4]%mod;
	}
	for(int i=0;i<n;i++) printf("%d ", (n-i-cnt3<0)?0:ans[n-i-cnt3]);
}