P1879 [USACO06NOV]玉米田Corn Fields

农场主John新买了一块长方形的新牧场，这块牧场被划分成M行N列(1 ≤ M ≤ 12; 1 ≤ N ≤ 12)，每一格都是一块正方形的土地。John打算在牧场上的某几格里种上美味的草，供他的奶牛们享用。

遗憾的是，有些土地相当贫瘠，不能用来种草。并且，奶牛们喜欢独占一块草地的感觉，于是John不会选择两块相邻的土地，也就是说，没有哪两块草地有公共边。

John想知道，如果不考虑草地的总块数，那么，一共有多少种种植方案可供他选择？（当然，把新牧场完全荒废也是一种方案）

我用的最最暴力的方法。nm2m*2m的复杂度一看就很吓人啊，但是数据好水水。。。

我的循环枚举有一部分浪费在了判断是否合法上，也就是那个m。

如果可以去掉的话就是正解了喵喵喵。。。

怎么O(1)判断有解呢？

看来位运算还是不太会啊。。。

首先可以用一个二进制数存储每一行的合法状态。

\((ok(i)<<=1)|=x\)

然后怎么样判断对于第i行，我们现在枚举的状态j是否合法？

1,先看对于j这个状态每一位和它的前一位又没有相交（即同为1）

\(if(j　and　(j>>1)==0)--> j 　is　ok\)

2,再看j这个状态是否符合ok[i]

\(if(j　and　～(ok[i])) -->j　is 　not 　ok\)

ok了，以后尽量多用整行的二进制数位运算。

再安利大佬同桌@顾z的题解喽，喵喵喵。。。

code：

#include <iostream>

#include <cstdio>

using namespace std;

const int mod=100000000;

const int wx=17;

inline int read(){

	int sum=0,f=1; char ch=getchar();

	while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();}

	while(ch>='0'&&ch<='9'){sum=(sum<<1)+(sum<<3)+ch-'0'; ch=getchar();}

	return sum*f;

}

int n,m;

int ok[wx][wx];

int f[wx][1<<wx];

int ans;

int main(){

	n=read(); m=read();

	for(int i=1;i<=n;i++)

		for(int j=1;j<=m;j++)

			ok[i][j]=read();

	int WX=(1<<m);

	for(int i=0;i<WX;i++){

		int flag=0;

		for(int j=1;j<=m;j++){

			if( (i&(1<<(j-1))) && (!ok[1][j]) ) {flag=1; break;}

			if(j>=2)if( (i&(1<<(j-1))) && (i&(1<<(j-2))) ) {flag=1; break;}

		}

		if(!flag)f[1][i]=1;

	}

	for(int i=2;i<=n;i++){ //枚举每一行

		for(int j=0;j<WX;j++){ //m枚举当前行的状态

			 int flag=0;

		     for(int k=1;k<=m;k++){

				if( (j&(1<<(k-1))) && (!ok[i][k]) ) {flag=1; break;}

				if(k>=2)if( (j&(1<<(k-1))) && (j&(1<<(k-2))) ) {flag=1; break;}

			 }

			 if(flag) continue;

			 for(int k=0;k<WX;k++){

			 	int flag=0;

			 	for(int l=1;l<=m;l++){

			 		if( (j&(1<<(l-1))) && (k&(1<<(l-1))) ){flag=1; break;}

			 		if( (k&(1<<(l-1))) && (!ok[i-1][l]) ){flag=1; break;}

			 	}

			 	if(flag)continue;

			 	f[i][j]=(f[i][j]+f[i-1][k])%mod;

			 }

		}

	}

	for(int i=0;i<WX;i++){

		ans=(ans+f[n][i])%mod;

	}

	printf("%d\n",ans);

	return 0;

}