【SSL1382】车
Description
在n*n(n≤20)的方格棋盘上放置n个车(可以攻击所在行、列)，有些格子不能放,求使它们不能互相攻击的方案总数。
Input
第一行为棋盘的大小n
第二行为障碍的数量m
第三行到第m+3为m个障碍
Output
总数
Sample Input
4
2
1 1
2 2
Sample Output
14
思路：
我们可以设
f
[
i
]
[
j
]
f[i][j]
f[i][j]为当前第
i
,
j
i,j
i,j这个位置放的答案，虽然这样可行，但我们想到可以优化，那就是状压DP
状压DP就是把维数降一，把其中一维用二进制表示，转换成十进制存到数组里
那我们思考这道题怎么状压
我们用
a
a
a数组表示这一行障碍的状态，则它的转移就是
a
[
x
]
+
=
p
o
w
[
y
−
1
]
a[x]+=pow_[y-1]
a[x]+=pow[y−1]
其中
p
o
w
pow
pow代表二的几次方（注意：我们这里是从右到左看）
接下来我们考虑怎样转移：
首先我们要枚举它所有的状态个数，即
p
o
w
[
n
]
−
1
pow[n]-1
pow[n]−1
我们要考虑当前的障碍状压，所以我们要用一个
c
c
c来记录当前的行数，然后我们就得出这样一个转移方式：
for(long long t=i&~a[c]; t; t-=VL_lowbit(t))
f[i]+=f[i^VL_lowbit(t)];
其中1代表不能放（以放或障碍），0代表能放（还未放）
&是用来枚举转移到当前状态的状态所做出的运算，取反是：假设现在有个障碍01，取反后就是10，它和当前状态（假设是11）&一下，转移的状态就是10。（原理：0和1&是0）
代码：
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<queue>
#include<stack>
#include<map>
#include<cstring>
using namespace std;
long long n, m;
long long pow_[10010001], a[10101010], f[11001100]={1};
long long VL_lowbit(long long x){return x & -x;}
int main(){
scanf("%lld%lld", &n, &m);
pow_[0]=1;
for(long long i=1; i<=n; i++)
pow_[i]=pow_[i-1]*2;
for(long long i=1; i<=m; i++)
{
long long x, y;
scanf("%lld%lld", &x, &y);
a[x]+=pow_[y-1];
}
for(long long i=1; i<pow_[n]; i++)
{
long long c=0;
for(long long t=i; t; t-=VL_lowbit(t))
c++;
for(long long t=i&~a[c]; t; t-=VL_lowbit(t))
f[i]+=f[i^VL_lowbit(t)];
}
printf("%lld", f[pow_[n]-1]);
return 0;
}