n皇后问题再经典不过了，想必大家也听说过。
再简单说一下吧，就是一个n*n的棋盘，放置n个皇后，使得竖着不攻击，横着不攻击，斜着不攻击。求有多少种方法。

（国际象棋不是这么玩的呀 ）
向来网上都是经典的题目配经典的解法，用一个矩阵记录哪里放了，回溯一下，每一次遍历每一个皇后，判断会不会被攻击。。。
然而，比蜗牛🐌还慢！！数据大一丁点，宇宙毁灭了都算不完，可见得有多慢啊！！
复杂度为：O(nⁿ)你说可怕不可怕
（⊙ｏ⊙）
能不能快一点？可以滴：

---

先来代码：

（讲真，下面代码简直是一个二进制操作套餐。。。）

#include <bits/stdc++.h>using namespace std;
typedef long long ll;ll sum, mark;
void test(ll row, ll ld, ll rd)
{if(row != mark){ll pos = mark & ~(row | ld | rd);while(pos) {ll p = pos & -pos; pos -= p; test(row + p, (ld + p) << 1, (rd + p) >> 1); }}elsesum++;
}int main()
{ios::sync_with_stdio(false);int n;cin >> n;sum = 0, mark = 1;mark = (mark << n) - 1;test(0, 0, 0);cout<<sum;return 0;
}

我看了是一脸懵？？？(⊙_⊙)？什么玩意，这这这，，
在一位大佬的指点下，终于明白了。我的理解：
首先这个算法是从上往下，从右往左扫描的
其次，我们细细看一看：
mark，是有n个1（二进制）的数
比如

n	mark	mark的二进制
1	1	1
2	3	11
3	7	111
4	15	1111

或者说，把棋盘其中一行的每一格写上1，这一行对应的10进制就是mark。
如果还没有明白的话，请温习二进制===
重点部分来了：
当当当敲黑板！！
看一看test函数
row啥意思呢？ 其实这个名字我觉得不好，应该叫col，表示哪些列有坑（坑代表在这里会被攻击）。有坑的列为1，没有的为0.
ld代表左斜的坑。额，咋说捏，上图吧。

假设遍历到了第3行，这时的ld是0010.
其实是10010，但是代码里给&mark，所以前面不管怎样，都被忽略了，所以把它当成0010吧。其实更建议在传参的时候就给&一下，以免数太大出各种问题。。
rd代表右斜的坑。一样的，上面理解了这里也能理解吧

如果row==mark，说明都放满了。恭喜恭喜啦啦啦！！找到了一个成功方案(～￣▽￣)～(●ˇ∀ˇ●)φ(゜▽゜*)♪
否则呢，只能苦苦滴继续算了≡(▔﹏▔)≡
pos代表这行哪些位置能放，能放即为1，不能就是0.
当然，不能放的超出棋盘啦，所以要&一下
Then，遍历哪里能放，，
pos & -pos取得最后一个为1的位，就是lowbit。
如果懂的话，可以无视这段内容：

---

-pos会把pos取反+1（不知道的童鞋请温习补码），那么末尾的那些0会咋样呢？
取反码，末尾0段都变成1了，再加1，全往前进位，所以变成了10000…
前面呢？既然取反，所以全都变成0了（因为0&1=0）。
举个栗子：
pos=010100
~pos=101011
((~pos)+1)=-pos=101100
-pos&pos=100

---

那么遍历了这个1，需要把它去掉，否则后果不堪设想（就是传说中的while(1)）
然后呢，递归。
因为这一列已经放了，所以要在这里标一个1，说明如果往这里再放皇后将会被干掉。
那么接下来两个参数，，
首先，左斜斜率为1，自然y往下一点对应的x也会往左，所以左移。记得别忘了加上p。
右斜斜率为-1，每一次y往下对应的x会往右，所以右移。
栗子：

是不是有一点乱，，那么，换一个更简单的栗子吧

然后呢，就继续回溯吧。。。直到算出来
改版代码：

// nQueen.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//#include <bits/stdc++.h>using namespace std;
typedef long long ll;ll sum, mark;
//mark是有n个1（二进制）的数
//sum是解
void test(ll col, ll ld, ll rd)
//col是哪些列有皇后
//ld是当前行哪些位置会被左斜攻击
//rd是当前行哪些位置会被右斜攻击
{if (col != mark)//如果没算完的话，只能继续算了呜呜呜{ll pos = mark & ~(col | ld | rd);//获取哪些位置能放while (pos){ll p = pos & -pos;//取得最靠后的1位pos -= p;//去掉test(col | p, ((ld | p) << 1) & mark/*谨防溢出*/, (rd | p) >> 1);//计算下一行}}elsesum++;//啦啦啦啦算到了一个解啦啦啦啦
}int main()
{ios::sync_with_stdio(false);int n;cin >> n;sum = 0, mark = 1;mark = (mark << n) - 1;//以上初始化↑test(0, 0, 0);//计算cout << sum;//输出return 0;
}// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件

已知数据：（嘿嘿~其实这个是从网上抄滴）
1 1
2 0
3 0
4 2
5 10
6 4
7 40
8 92
9 352
10 724
11 2680
12 14200
13 73712
14 365596
15 2279184
16 14772512
17 95815104
18 666090624
19 4968057848
20 39029188884
21 314666222712
22 2691008701644
23 24233937684440
24 227514171973736
25 2207893435808352

---