互不侵犯

#include <bits/stdc++.h>
using namespace std;

const int N = 15;
int n,k;
long long f[N][N * N][1 << N];

int size(int s)
{
int cnt = 0;
for (; s; s >>= 1) {
cnt += s & 1;
}
return cnt;
}

bool check(int s)
{
if (s & (s << 1)) return false; //本集合内国王是否冲突
return true;
}

bool check(int s,int t) { //两行之间的国王是否冲突
if ((t & s) || (s & (t << 1)) || ((s << 1) & t)) return false;
return true;
}

int main() { ios::sync_with_stdio(false); cin >> n >> k; int m = 1 << n; f[0][0][0] = 1; //边界 //f[i][j][S]表示正在处理第i行，第i行放的格子集合为S,前i行共放了j个国王 for (int i = 1; i <= n + 1; i++) //行 for (int s = 0; s < m; s++) { // 枚举当前行的状态 if (check(s)) for (int t = 0; t < m; t++) { //枚举上一行的状态 if (check(t) && check(s,t)) { int sz = size(s); for (int j = sz; j <= k; j++) //国王个数 f[i][j][s] += f[i - 1][j - sz][t]; //由上一行转移来 } } } cout << f[n + 1][k][0]; }