时间限制：0.25s
空间限制：4M
题意：
在 n*n(n≤10)的棋盘上放 k (k<=n*n)个国王(可攻击相邻的 8 个格子)，求使它们无法互相攻击的方案数。
Solution：
采用状态压缩，用k位（k<=n）的二进制数1的位置代表棋盘放置的国王的位置.
先用预处理,求出statu[i]仅考虑一行时满足要求的方案,c[i]是statu[i]状态放置的棋子数.
f[i][j][p] 代表第i行放置状态为 p时且已经放置了j个棋子的方案数
状态转移方程：f[i][j][p]=Σf[i-1][j-c[j]][pp],(满足i-1行的pp与p不冲突)
判断p与pp是否冲突 只要满足
(p & pp) == 0 && (p << 1 & pp) == 0 && ( pp<< 1 & p) == 0
最后输出ans=Σf[n][k][pi]
参考代码：
#include <iostream>
#include <cstdio>
#define LL long long
using namespace std;
int powT[11];
int statu[1 << 10], c[1 << 10];
LL f[11][111][1 << 10];
int main() {
int n, k, tol = 0, t;
scanf ("%d %d", &n, &k);
for (int i = 0; i <= ( (1 << n) - 1); i++) {
if ( ( (i & (i >> 1) ) == 0) && ( (i & (i << 1) ) == 0) ) {
statu[++tol] = i;
for (t = i; t > 0; t >>= 1)
if (t & 1) c[i]++;
}
}
for (int i = 1; i <= tol; i++)
f[1][c[statu[i]]][statu[i]] = 1;
for (int i = 2; i <= n; i++) {
for (int j = 0; j <= k; j++)
for (int pu = 1; pu <= tol; pu++)
for (int pv = 1; pv <= tol; pv++) {
int p1 = statu[pu], p2 = statu[pv];
if (j >= c[p1] && (p1 & p2) == 0 && ( p1 << 1 & p2) == 0 && ( p2 << 1 & p1) == 0)
f[i][j][p1] += f[i - 1][j - c[p1]][p2];
}
}
LL ans = 0;
for (int i = 1; i <= tol; i++)
ans += f[n][k][statu[i]];
printf ("%lld", ans);
}
