题目链接：https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=14&page=show_problem&problem=1178
将棋盘旋转 \(45°\) 后，对角线转化为行和列，而奇数行和偶数行的棋盘互不影响，所以我们将奇数行和偶数行的棋盘拆开算
\(dp[i][j]\) 表示前 \(i\) 行放了 \(j\) 个象的方案数，发现每行的长度不一样，但每个长度有两个且长度从 \(1\) 到 \(n\) 连续，每种长度有两种(第 \(n\) 行可能一种)，而且行的排列方式对答案没有影响，所以可以按长度从小到大枚举行计算答案
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 55;
int n, k;
ll f[maxn][maxn], g[maxn][maxn];
ll read(){ ll s = 0, f = 1; char ch = getchar(); while(ch < ‘0‘ || ch > ‘9‘){ if(ch == ‘-‘) f = -1; ch = getchar(); } while(ch >= ‘0‘ && ch <= ‘9‘){ s = s * 10 + ch - ‘0‘; ch = getchar(); } return s * f; }
int main(){
while(scanf("%d%d", &n, &k) == 2 && n){
memset(f, 0, sizeof(f));
memset(g, 0, sizeof(g));
f[0][0] = 1;
for(int i = 1 ; i <= n ; ++i){
int len = i - !(i&1);
f[i][0] = 1;
for(int j = 1 ; j <= len && j <= k ; ++j){
f[i][j] = f[i-1][j] + f[i-1][j-1] * (len-j+1);
}
}
g[1][0] = 1;
for(int i = 2 ; i <= n ; ++i){
int len = i - (i&1);
g[i][0] = 1;
for(int j = 1 ; j <= len && j <= k ; ++j){
g[i][j] = g[i-1][j] + g[i-1][j-1] * (len-j+1);
}
}
ll ans = 0;
for(int i = 0 ; i <= k ; ++i){
ans += f[n][i] * g[n][k-i];
}
printf("%lld\n", ans);
}
return 0;
}