首先声明 ： 这是个很easy的题 可这和我会做有什么关系
题目大意：
在n*n的方格棋盘上放置n个车，某些格子不能放，求使它们不能互相攻击的方案总数。
注意：同一行或同一列只能有一个车，否则会相互攻击、
输入：
输入文件第一行，有两个数n, m ,n表示方格棋盘大小,m表示不能放的格子数量
下面有m行,每行两个整数,为不能放的格子的位置。
算法分析：
1. 显然这是个状压dp（好吧没有那么显然，但是是状压dp就完了） 状态很多而且给出的数据范围很小（这个题给出的20>=n）
2. 我们定义一个数组f[i]，表示第 i 个状态所满足的方案数
举个栗子： 1011 就可以表示当前行的状态为第二列还可以放车，而第一三四行已经在之前的状态中放车了（~~一列只能有一个车这不是显然吗~~)
3. 题中给出一个限制 ， 即有m个位置是不能放车的 ， 我们用a数组存储该位置
**这个地方就要按着状压dp自己的方式存储了**
再举个栗子： 如果第二行第三列有个障碍物 那么我们将a[2] += 1<<(3-1)(这里将a数组初始化为0 想象一下一个二进制串在是0的时候 就是 000000 如果要在第三列的位置加上障碍物 可以想象到就是000100 也就是0 + 1<<(3-1))
4. 在这个地方我们先提及一下lowbit数组 `int lowbit(int x){return x & -x;}`
lowbit数组的目的是求出x的二进制表示中最小位的1的位置
还是举个例子 101000 lowbit的结果就是1000
1100 lowbit的结果就是100
具体实现可参见度娘
lowbit数组具体用处我们已经了解了 那么lowbit数组有什么用呢？
再来回想一下我们定义的f数组 当前i表示状态 如果我们用 for(int i=S;i;i-=lowbit(i))cnt++;这样的代码
很轻松就可以求出当前状态中1的个数 ， 也就是当前状态已经放了的车的个数，以及当前为第几行 ，显然个数 = cnt = 第几行（一个n*n的方格，放n个车，每一行有且仅有一个车）
5.然后就可以进行动态转移方程了，具体方程如下
这里的i即枚举的当前行的每一个可能放的车（我们只知道当前行一定会放一个车，但是车在哪里我们并不清楚，因此枚举一遍并累加满足条件的方案书）
而a[cnt]则表示当前行的障碍物情况
刚才我们已经提过lowbit（i）可以求出最右边的i的位置 我们外层的i每次减去一个i 即进行当前行下个车可能位置的求解
注意一个小细节`a[cnt] & lowbit(i)`这里表示当前行障碍物并不与当前行的车位置冲突，可以在这里放车，即可以由上一行的状态转移过来
s = S^lowbit(i) ：S 异或 lowbit(i)即求出如果当前行车的位置在lowbit(i)那么上一行的状态就是s 然后累加到当前行的方案数即可
for(int i=S;i;i-=lowbit(i)){
if(!(a[cnt] & lowbit(i))){
int s=S^lowbit(i);
f[S]+=f[s];
}
}
AC代码
#include<bits/stdc++.h>
const int maxn=(1<<20)-1;
typedef long long LL;
LL f[maxn],a[25];
int lowbit(int x){return x & -x;};
int main(){
int n,m;scanf("%d%d",&n,&m);
for(int i=1;i<=m;++i){
int x,y;scanf("%d%d",&x,&y);
a[x]+=1<<(y-1);
}
f[0]=1;
int maxs=1<<n;
for(int S=1;S<=maxs;++S){
int cnt=0;
for(int i=S;i;i-=lowbit(i))cnt++;
for(int i=S;i;i-=lowbit(i)){
if(!(a[cnt] & lowbit(i))){
int s=S^lowbit(i);
f[S]+=f[s];
}
}
}
printf("%lld
",f[maxs-1]);
return 0;
}