51nod 1843 排列合并机【DP去重】Ender的模拟赛

题目描述

有两个1~n的排列A,B,序列C一开始为空,每次可以选择进行以下两种操作之一
1)若A不为空,则可取出A的开头元素放在序列C的末尾
2)若B不为空,则可取出B的开头元素放在序列C的末尾
这样当A,B皆为空时,C称为排列A,B的合并,其长度为2*n
记F(A,B)为A,B的所有可能合并的总数，两个合并数列不同当且仅当某一位不同
求对于所有可能的1~n的排列A,B,F(A,B)的和,mod 998244353
1<=n<=100
（51nod上mod是读入的）

题目分析：

考虑怎么样合并会重复，是有一段长度为2*len的合并序列，A占len，B占len，且A=B，这样调换A，B的顺序是一样的，称这样的串为好串，并且好串的前缀不能为好串。
考虑在A,B数列确定的情况下，用$f[i][j]$表示A选了i个，B选了j个的合并方案数。
有转移$f[i][j]=f[i-1][j]+f[i][j-1]-{\sum }_{d=1}^{s}g[d]\ast f[i-d][j-d]$
其中s为A[1,i]与B[1,j]的最长公共后缀长度，g[d]为用长度为d的两个相同串组成好串且前缀不为好串的方案数，由好串的定义可知，它等价于从(0,0)走到(d,d)，第一步向左，中途不能碰到x=y的方案数，于是有$g[d]=Catalan(d-1)$。

数列不定的情况下，无法得知公共后缀长度。我们需要增加一维$k$表示A[1,i]与B[1,j]中相同的数字个数。
有如下转移：

if(i<n)
	f[i+1][j][k]=(f[i+1][j][k]+1ll*f[i][j][k]*(n-i-j+k))%mod,
	f[i+1][j][k+1]=(f[i+1][j][k+1]+1ll*f[i][j][k]*(j-k))%mod;
if(j<n)
	f[i][j+1][k]=(f[i][j+1][k]+1ll*f[i][j][k]*(n-i-j+k))%mod,
	f[i][j+1][k+1]=(f[i][j+1][k+1]+1ll*f[i][j][k]*(i-k))%mod;

去重：$$f[i][j][k]-=\sum _{d=1}^k\left(\genfrac{}{}{0ex}{}{n-((i-d)+(j-d)-(k-d))}{d}\right)\ast d!\ast g[d]\ast f[i-d][j-d][k-d]$$
$f[n][n][n]$即为答案。循环枚举k的时候注意$k\in [\max (0,i+j-n),\min (i,j)]$，因为$i+j-k\le n$，所以$k\ge i+j-n$。

Code：

#include<bits/stdc++.h>
#define maxn 105
using namespace std;
const int mod = 998244353;
int n,f[maxn][maxn][maxn],c[maxn<<1][maxn<<1],Cat[maxn],fac[maxn];
int main()
{
	freopen("R.in","r",stdin);
	freopen("R.out","w",stdout);
	scanf("%d",&n);
	c[0][0]=Cat[0]=fac[0]=1;
	for(int i=1;i<=2*n;i++){
		c[i][0]=c[i][i]=1;
		for(int j=1;j<i;j++) c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;
	}
	for(int i=1;i<=n;i++) Cat[i]=(c[2*i][i]-c[2*i][i-1])%mod,fac[i]=1ll*fac[i-1]*i%mod;
	f[0][0][0]=1;
	for(int i=0;i<=n;i++)
		for(int j=0;j<=n;j++)
			for(int k=max(0,i+j-n);k<=min(i,j);k++){
				for(int d=1;d<=k;d++)
					f[i][j][k]=(f[i][j][k]-1ll*c[n-i-j+k+d][d]*f[i-d][j-d][k-d]%mod*Cat[d-1]%mod*fac[d])%mod;
				if(f[i][j][k]){
					if(i<n)
						f[i+1][j][k]=(f[i+1][j][k]+1ll*f[i][j][k]*(n-i-j+k))%mod,
						f[i+1][j][k+1]=(f[i+1][j][k+1]+1ll*f[i][j][k]*(j-k))%mod;
					if(j<n)
						f[i][j+1][k]=(f[i][j+1][k]+1ll*f[i][j][k]*(n-i-j+k))%mod,
						f[i][j+1][k+1]=(f[i][j+1][k+1]+1ll*f[i][j][k]*(i-k))%mod;
				}
			}
	printf("%d\n",(f[n][n][n]+mod)%mod);
}