https://www.luogu.org/problemnew/show/P1879

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

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

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

输入输出格式

输入格式：

 

第一行：两个整数M和N，用空格隔开。

第2到第M+1行：每行包含N个用空格隔开的整数，描述了每块土地的状态。第i+1行描述了第i行的土地，所有整数均为0或1，是1的话，表示这块土地足够肥沃，0则表示这块土地不适合种草。

 

输出格式：

 

一个整数，即牧场分配总方案数除以100,000,000的余数。

 

题意：n*m矩阵中有些点可以选，有些不能选，要求在可以选的中选若干个点，使得没有两个点相邻，求方案数。

思路：状压dp模板题，每一行作为一个阶段，设f(i,j):前i行，并且第i行压位二进制为state数组第j个，对应的方案数。

f(i,j)=Σf(i-1,k),k∈fit(j,k)

#include<bits/stdc++.h>
using namespace std;
#define mod 100000000

int n,m,field[15];
int state[1<<15],tot;
int f[15][1<<15];//注意第二维是在state[]中的下标，而非实际二进制 

int main()
{
//	freopen("input.in","r",stdin);
	int x;
	cin>>n>>m;
	for(int i=0;i<n;i++)for(int j=m-1;j>=0;j--)
	{
		cin>>x;
		if(x)field[i]|=(1<<j);
	}
	for(int i=0;i<(1<<m);i++)if(!(i&(i<<1)))state[tot++]=i;
	
	for(int i=0;i<tot;i++)if((field[0]|state[i])==field[0])f[0][i]=1;
	for(int i=1;i<n;i++)
	{
		for(int j=0;j<tot;j++)
		{
			if((field[i]|state[j])==field[i])
				for(int k=0;k<tot;k++)
				{
					if(!(state[j]&state[k]))f[i][j]=(f[i][j]+f[i-1][k])%mod;
				}
		}
	}
	int ans=0;
	for(int i=0;i<tot;i++)ans=(ans+f[n-1][i])%mod;
	cout<<ans<<endl;
	exit(0);
}