题目链接：

题目大意;

在N×N的棋盘里面放K个国王，使他们互不攻击，共有多少种摆放方案。国王能攻击到它上下左右，以及左上左下右上右下八个方向上附近的各一个格子，共8个格子。

思路：

状态压缩，预处理出每一行的合法状态，连续的两个1在一起的状态为不合法状态。

预处理出从上一行到下一行的合法情况，直接每一行推过来即可。

1 #include
     
       2 #define IOS ios::sync_with_stdio(false);//不可再使用scanf printf 3 #define Max(a, b) ((a) > (b) ? (a) : (b))//禁用于函数，会超时 4 #define Min(a, b) ((a) < (b) ? (a) : (b)) 5 #define Mem(a) memset(a, 0, sizeof(a)) 6 #define Dis(x, y, x1, y1) ((x - x1) * (x - x1) + (y - y1) * (y - y1)) 7 #define MID(l, r) ((l) + ((r) - (l)) / 2) 8 #define lson ((o)<<1) 9 #define rson ((o)<<1|1)10 #define Accepted 011 #pragma comment(linker, "/STACK:102400000,102400000")//栈外挂12 using namespace std;13 inline int read()14 {15     int x=0,f=1;char ch=getchar();16     while (ch<'0'||ch>'9'){
   if (ch=='-') f=-1;ch=getchar();}17     while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}18     return x*f;19 }20 typedef long long ll;21 const int maxn = 2000000 + 10;22 const int MOD = 1000000007;//const引用更快，宏定义也更快23 const int INF = 1e9 + 7;24 const double eps = 1e-10;25 const double pi = acos(-1);26 27 bool Map[520][520];28 bool no[520];//判断状态i是否不合法29 ll dp[10][520][100];//dp[i][j][k] 表示第i行状态为j，且当前放置的数目为k30 int n, k;31 void init()32 {33     for(int x = 0; x < (1<
      
       > n >> k;60     init();61     for(int i = 0; i < (1<