#include #include using namespace std; long long sta[2005], sit[2005], f[15][2005][105]; int n, k, cnt; void dfs(int x, int num, int cur) { if (cur >= n) { // 有新的合法状态 sit[++cnt] = x; sta[cnt] = num; return; } dfs(x, num, cur + 1); // cur位置不放国王 dfs(x + (1 << cur), num + 1, cur + 2); // cur位置放国王,与它相邻的位置不能再放国王 } bool compatible(int j, int x) { if (sit[j] & sit[x]) return false; if ((sit[j] << 1) & sit[x]) return false; if (sit[j] & (sit[x] << 1)) return false; return true; } int main() { cin >> n >> k; dfs(0, 0, 0); // 先预处理一行的所有合法状态 for (int j = 1; j <= cnt; j++) f[1][j][sta[j]] = 1; for (int i = 2; i <= n; i++) for (int j = 1; j <= cnt; j++) for (int x = 1; x <= cnt; x++) { if (!compatible(j, x)) continue; // 排除不合法转移 for (int l = sta[j]; l <= k; l++) f[i][j][l] += f[i - 1][x][l - sta[j]]; } long long ans = 0; for (int i = 1; i <= cnt; i++) ans += f[n][i][k]; // 累加答案 cout << ans << endl; return 0; }