题意：一个矩阵里有很多格子，每个格子有两种状态，可以放牧和不可以放牧，可以放牧用1表示，否则用0表示，在这块牧场放牛，要求两个相邻的方格不能同时放牛，即牛与牛不能相邻。问有多少种放牛方案(一头牛都不放也是一种方案)
分析：每一行看做一个状态，用一个二进制数来表示，每一行会排出牛和牛相邻的情况；由上一行转移到下一行的条件就是这一行和上一行不会存在1在同一列，也就是与操作后为0，
状态表示： dp[state][i] 表示 在状态为state情况下第i行可以满足的方案数
状态转移：DP[state][i] += dp[state'][i - 1] (state & state' == 0）
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int Mod = ;
int state[];
int dp[][], cur[];
int n, m, total, top;
inline bool is_ok(int x)
{
if (x & (x << )) // 如果存在相邻的1返回0
return ;
return ;
}
void init()
{
top = ;
total = << n;
for (int i = ; i < total; i++)
if(is_ok(i))
state[++top] = i;
}
inline bool fit(int x, int i)
{
if (x & cur[i])
return ;
return ;
}
int main()
{
while (scanf("%d%d", &m, &n) != EOF)
{
init();
int num;
for(int i = ; i <= m; i++)
{
cur[i] = ;
for(int j = ; j <= n; j++)
{
scanf("%d", &num);
if (num == )
cur[i] += ( << (n - j));
//这里之前不明白为什么num == 0的时候开始计数，把不允许放牧的地方都设为1，而允许放牧的就是0，所以判断当前状态与哪些标准状态匹配时候只需判断 & 之后是否为0，因为只要是非0，一定是不行的，在那一个点下不允许放牧，标准却可以放牧。 当前状态可以放牧，即为0，那么标准状态下，这一个位置放不放都可以，所以标准下0,1都可以
}
}
memset(dp, , sizeof(dp));
for (int i = ; i <= top; i++)
{
if (fit(state[i], )) // 先判断第一行的情况，state[1] = 0,这也是可以的
dp[][i] = ;
} for (int i = ; i <= m; i++)
{
for(int k = ; k <= top; k++) // 判断第 i 行可以由哪些标准状态
{
if(!fit(state[k], i)) continue;
for (int j = ; j <= top; j++)
{
if(!fit(state[j], i - )) continue; //选择i-1可以的标准状态
if (state[k] & state[j]) continue; // 没有列相邻的1
dp[i][k] += dp[i - ][j];
dp[i][k] %= Mod;
}
}
}
int ans = ;
for (int i = ; i <= top; i++)
{
ans += dp[m][i];
ans %= Mod;
}
printf("%d\n", ans);
}
return ;
}