车

Time Limit:1000MS Memory Limit:65536K
Total Submit:113 Accepted:46

Description

在n*n(n≤20)的方格棋盘上放置n个车(可以攻击所在行、列)，有些格子不能放,求使它们不能互相攻击的方案总数。

Input

第一行为棋盘的大小n
第二行为障碍的数量m
第三行到第m+3为m个障碍

Output

总数

Sample Input

4
2
1 1
2 2

Sample Output

14

分析：

明明学长讲状压 D P DP DP原理时我还听得挺明白 的 Q w Q … … QwQ…… QwQ……
结果 c o d e code code一堆位运算好复杂 Q w Q … … QwQ…… QwQ……
读题 此题 n , m n,m n,m都很小 并且是求方案总数 就是用状压 D P DP DP了
a a a数组表示当前行的障碍 那么转移方程：
a [ x ] + = p [ y − 1 ] a[x]+=p[y-1] a[x]+=p[y−1]
p p p表示 2 2 2的几次方 然后用 k k k表示当前行数 枚举 t a ta ta的所有状态个数
y y s y yysy yysy这个转移方程的 异或(^) 和 按位与(&) 十分巧妙 好好理解 Q a Q QaQ QaQ(真叫人头大)

for(long long j=i&~a[k];j;j-=lowbit(j))
			f[i]+=f[i^lowbit(j)];

CODE：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
long long n,m,p[1000005],a[1000005];
long long f[1000005]={1};
long long lowbit(long long x){
	return x&(-x);
}
int main(){
	scanf("%lld%lld",&n,&m);
	p[0]=1; 
	for(long long i=1;i<=n;i++)
		p[i]=p[i-1]*2;
	for(long long i=1;i<=m;i++)
	{
		long long x,y;
		scanf("%lld%lld",&x,&y);
		a[x]+=p[y-1];   //障碍转移方程
	}
	for(long long i=1;i<p[n];i++)
	{
		long long k=0;
		for(long long p=i;p;p-=lowbit(p))
			k++;  //统计行数
		for(long long j=i&~a[k];j;j-=lowbit(j))
			f[i]+=f[i^lowbit(j)]; //枚举状态
	}
	printf("%lld",f[p[n]-1]);
	return 0;
}