当前位置: 首页 > 工具软件 > Ender > 使用案例 >

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

毕胡非
2023-12-01

题目描述

有两个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 ] f[i][j] f[i][j]表示A选了i个,B选了j个的合并方案数。
有转移 f [ i ] [ j ] = f [ i − 1 ] [ j ] + f [ i ] [ j − 1 ] − ∑ d = 1 s g [ d ] ∗ f [ i − d ] [ j − d ] f[i][j]=f[i-1][j]+f[i][j-1]-\sum_{d=1}^sg[d]*f[i-d][j-d] f[i][j]=f[i1][j]+f[i][j1]d=1sg[d]f[id][jd]
其中s为A[1,i]与B[1,j]的最长公共后缀长度,g[d]为用长度为d的两个相同串组成好串且前缀不为好串的方案数,由好串的定义可知,它等价于从(0,0)走到(d,d),第一步向左,中途不能碰到x=y的方案数,于是有 g [ d ] = C a t a l a n ( d − 1 ) g[d]=Catalan(d-1) g[d]=Catalan(d1)

数列不定的情况下,无法得知公共后缀长度。我们需要增加一维 k k 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 ] − = ∑ d = 1 k ( n − ( ( i − d ) + ( j − d ) − ( k − d ) ) d ) ∗ d ! ∗ g [ d ] ∗ f [ i − d ] [ j − d ] [ k − d ] f[i][j][k]-=\sum_{d=1}^k{n-((i-d)+(j-d)-(k-d))\choose d}*d!*g[d]*f[i-d][j-d][k-d] f[i][j][k]=d=1k(dn((id)+(jd)(kd)))d!g[d]f[id][jd][kd]
f [ n ] [ n ] [ n ] f[n][n][n] f[n][n][n]即为答案。循环枚举k的时候注意 k ∈ [ max ⁡ ( 0 , i + j − n ) , min ⁡ ( i , j ) ] k\in[\max(0,i+j-n),\min(i,j)] k[max(0,i+jn),min(i,j)],因为 i + j − k ≤ n i+j-k\le n i+jkn,所以 k ≥ i + j − n k\ge i+j-n ki+jn

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);
}
 类似资料: