AT1879 2 つの山札

仙题+1

考虑这样子的序列是不是把(a)和(b)的元素放到一个网格图上然后从左上走到右下。。。

然后问题转换成了怎么去掉重复的。

卡特兰数直接求就行了。

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<iostream>
using namespace std;
#define re register
#define ll long long
inline int gi(){
	int f=1,sum=0;char ch=getchar();
	while(ch>'9' || ch<'0'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0' && ch<='9'){sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();}
	return f*sum;
}
const int N=4010,Mod=1e9+7;
int f[N][N],a[N],b[N],n,fac[N],inv[N],fai[N];
int C(int n){return 1ll*fac[n<<1]*fai[n]%Mod*fai[n+1]%Mod;}
int main(){
	n=gi();fac[0]=inv[0]=inv[1]=fai[0]=1;int M=n<<1;
	for(int i=1;i<=n;i++)a[i]=gi();
	for(int i=1;i<=n;i++)b[i]=gi();
	for(int i=1;i<=M;i++)fac[i]=1ll*fac[i-1]*i%Mod;
	for(int i=2;i<=M;i++)inv[i]=1ll*(Mod-Mod/i)*inv[Mod%i]%Mod;
	for(int i=1;i<=M;i++)fai[i]=1ll*fai[i-1]*inv[i]%Mod;
	f[1][1]=1;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++){
			if(i!=1 || j!=1)f[i][j]=(f[i][j-1]+f[i-1][j])%Mod;
			if(a[i]==b[j])
				for(int k=1,step=0;k<i && k<j;k++)
					if(a[i-k]==b[j-k])
						f[i][j]=(f[i][j]-1ll*C(step)*f[i-k][j-k]%Mod+Mod)%Mod,step++;
		}
	printf("%d
",f[n][n]);
	return 0;
}