Educational Codeforces Round 170 D 题纯 DP 思路
发现只有花色为 1 1 1 的牌比较特殊，其余花色的牌，要么跟与自己花色相同的牌比，要么跟 1 1 1 比。
设 g k , i g_{k,i} gk,i 表示考虑到 1 ∼ k 1\sim k 1∼k 这些花色的牌，并且 2 ∼ k 2\sim k 2∼k 这些花色的牌全部完成合法配对 ，花色为 1 1 1 的牌 A A A 手里还剩 i i i 张，B手里一张没有的方案数。
先只考虑 k ≥ 2 k\geq 2 k≥2 的情况，枚举这副牌， B B B 消耗了几张花色为 1 1 1 的牌。
假如设 f i , j f_{i,j} fi,j 表示从小到大分配一副相同花色的牌，其中 A A A 的每一张牌都完成了配对， B B B 还剩下 j j j 张牌需要配对的方案数。
那么， g k , i = ∑ j g k − 1 , i + j × f m , j g_{k,i}=\sum_j g_{k-1,i+j}\times f_{m,j} gk,i=∑jgk−1,i+j×fm,j
发现 $f_{i,j} $ 的值同样可以表示，从大到小分配一副相同花色的牌，其中 B B B 的每一张牌都完成了配对， A A A 还剩下 j j j 张牌需要配对的方案数。
那么 g 1 , i = f m , i g_{1,i}=f_{m,i} g1,i=fm,i 。
int n, m;
Z f[N][N], g[N][N];
void solve(){
cin >> n >> m;
f[0][0] = 1;
for(int i = 1; i <= m; i ++){
for(int j = 0; j <= i; j ++){
if(j != m) f[i][j] += f[i - 1][j + 1];
if(j) f[i][j] += f[i - 1][j - 1];
// cout << i << ' ' << j << ' ' << f[i][j] << '\n';
}
}
for(int i = 0; i <= m; i ++){
g[1][i] = f[m][i];
}
for(int k = 2; k <= n; k ++){
for(int i = 0; i <= m; i ++){
for(int j = 0; i + j <= m; j ++){
g[k][i] += g[k - 1][i + j] * f[m][j];
}
}
}
cout << g[n][0] << '\n';
}