Card Game

watersail / 2024-10-19 / 原文

沉睡的记忆轻轻将你唤醒。记得三年前的五一，正是关于卡特兰数的折线法证明，同时兼容着【数形结合】和【正难则反】的思想，刷新了你对OI的认知
将卡牌的匹配关系视为括号序列，也与【前缀和非负】的感受相关。而合法的括号序列数又可以用卡特兰数来刻画。$Cat_{n}=\frac{C^{n}_{2n}}{n+1}=C^{n}_{2n}-C^{n+1}_{2n}$，后者是到(n-1,n+1)的方案数，与非法方案构成双射；由于其关于二叉树的中序遍历，因此也可以用${\textstyle \sum_{i=1}^{n}}H_{i-1}H_{n-i}$的递推公式求解
得到了这一关键提示后，也是成功独立做出这道题啦~
【调试程序】滚动数组的清空

点击查看代码

#include <bits/stdc++.h>
using namespace std;
const int mod=998244353;
long long f[2][505][505],g[505][505],h[2][505][505];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n,m;
	cin>>n>>m;
	f[0][0][0]=1;
	for(int i=1;i<=m;i++)
	{
		memset(f[i&1],0,sizeof(f[i&1]));
		for(int j=0;j<=i;j++)
		{
			for(int k=0;j+k<=i;k++)
			{
				if(k==0)
				{
					if(j)
					{
						f[i&1][j][k]=f[i&1^1][j-1][k];
					}
				}
				f[i&1][j][k]+=f[i&1^1][j][k+1];
				//add ')'
				if(k)
				{
					f[i&1][j][k]+=f[i&1^1][j][k-1];
				}//add '('
				f[i&1][j][k]%=mod;
			}
		}
	}
	/*
	for(int j=0;j<=m;j++)
	{
		cout<<j<<':'<<f[m][j][0]<<endl;
	}
	*/
	h[0][0][0]=1;
	for(int i=1;i<=m;i++)
	{
		memset(h[i&1],0,sizeof(h[i&1]));
		for(int j=0;j<=i;j++)
		{
			for(int k=0;j+k<=i;k++)
			{
				if(j)
				{
					h[i&1][j][k]=h[i&1^1][j-1][k];
				}//add'('
				if(j==0)
				{
					if(k)
					{
						h[i&1][j][k]+=h[i&1^1][j][k-1];
					}
				}
				h[i&1][j][k]+=h[i&1^1][j+1][k];
				h[i&1][j][k]%=mod;
				//add')'
			}
		}
	}
	/*
	for(int j=0;j<=m;j++)
	{
		cout<<j<<':'<<h[m][j][0]<<endl;
	}
	*/
	g[1][0]=1;
	for(int j=2;j<=n;j++)
	{
		for(int k=0;k<=m;k++)
		{
			for(int l=0;l<=k;l++)
			{
				g[j][k]+=(g[j-1][k-l]*h[m&1][l][0]%mod);
			}
			g[j][k]%=mod;
		}
	}
	long long ans=0;
	for(int i=0;i<=m;i+=2)
	{
		ans=ans+g[n][i]*f[m&1][i][0]%mod;
	}
	cout<<ans%mod<<endl;
	return 0;
}