SGU_224

    这个题目由于状态总数很大，但最后的结果又比较小，所以相比用状态压缩dp就很难搞定了，还是直接用dfs比较好。

    由于皇后每行只能放一个，我们不妨逐行递推。受Matrix67的启发，其实不必开数组去记录哪一条斜线上已经放了皇后，我们可以直接用一个变量比如ls来表示前面放置的皇后的左下斜线覆盖了当前这行的哪些位置（ls的某个二进制位为1表示这个位置被覆盖了，为0表示没有被覆盖），这样如果这行不放皇后的话，下一行的ls就是ls<<1，如果放置皇后的话也是类似的。这样用三个变量就可以描述前面放置的皇后的列、左斜线、右斜线覆盖了这行的哪些位置，进而能够很方便的知道这行上还有哪些位置可以放置皇后。

    另附Matrix67写N皇后问题的文章：。

#include
     
      #include
      
       int N, K, ans;void dfs(int cur, int num, int cs, int ls, int rs){    int i, st = cs | ls | rs;    if(cur == N)    {        if(num == K)            ++ ans;        return ;    }    dfs(cur + 1, num, cs, ls << 1, rs >> 1);    if(num < K)        for(i = 0; i < N; i ++)            if((st & (1 << i)) == 0)                dfs(cur + 1, num + 1, cs | (1 << i), (ls | (1 << i)) << 1, (rs | (1 << i)) >> 1);}void solve(){    ans = 0;    dfs(0, 0, 0, 0, 0);    printf("%d\n", ans);}int main(){    while(scanf("%d%d", &N, &K) == 2)    {        solve();    }    return 0;}