- 沉睡的记忆轻轻将你唤醒。记得三年前的五一，正是关于卡特兰数的折线法证明，同时兼容着【数形结合】和【正难则反】的思想，刷新了你对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;
}
