https://www.luogu.org/problemnew/show/P1879
题意：n*m的农田，有些格子可以放牧用1表示，不能放牧的用0表示。要求不能时相邻的格子都有牛。
用二进制来表示状态：假设存在某种情况 1001，1,4可以放牛，2,3不可以。该种情况化为10进制就是5.
对于一个列数为m，可能出现的方案为11.1...1（m个1）。即：++....结果为：-1；而对于这-1中情况，1于1相邻的要去掉（代码注释有）.
对于样列第一行：1 1 1：可能出现的结果有0 0 0，0 0 1，0 1 0，0 1 1.....
对于样列第二行 0 1 1：可能出现的结果为有0 0 0，0 1 0；
DP的思路在于推导：在推导之前要确保：在矩阵中为0的格子是不能放牧的，只有为1的格子才能变为0或1.所以对于样列第二行011，像111，100，110等这种情况是不存在的，所以要去掉（代码注释有）.
推导：假设第i行的情况数为x，第i+1行的情况数为y。当第i+1行出现第1种情况时：第i行x种情况中满足的情况数，当第当第i+1行出现第2种情况时:第i行x种情况中满足的情况数，...当第i+1行出现第y中情况时:第i行x种情况中满足的情况数.（上下的1也不能相邻）
即：dp[i][state(j)]=dp[i-1][state(k1)]+dp[i-1][state(k2)]+......+dp[i-1][state(kn)]。dp[i][state(j)].表示：第i+1行出现第state（j）情况。dp[i-1][state(k)]表示：第i-1行，第state（k）种情况（满足条件的）.
#include<bits/stdc++.h>
using namespace std;
int dp[20][4096];///20表示20行，这里n最大只有12，开大一些防出错。4096=1<<12（最多的情况数）。
int cur[20];///每一行的状态，需要该数组与state[]比较，排除格子为0发生变化的情况。
int state[4096],top;///满足1与1不相邻的情况。
int n,m,num;
const int mod=100000000;void init()
{top=0;int total=(1<<m);for(int i=0;i<total;i++)///找出1与1不相邻的情况，只要移位就行。如若有1与相邻，肯定会有1&1，则数!=0；if(!(i&i<<1)) state[top++]=i;
}
bool flag(int i,int j)
{if(i&cur[j]) return 0;return 1;
}
int main()
{cin>>n>>m;init();memset(dp,0,sizeof(dp));/*for(int i=0;i<top;i++)cout<<state[i]<<" ";*/for(int i=1;i<=n;i++){cur[i]=0;for(int j=1;j<=m;j++){cin>>num;if(num==0) cur[i]+=(1<<(m-j));/**flag()函数是从已满足1与1不相邻的情况中找出与原情况不矛盾的列子.拿样列：0 1 0.按照程序计算后，cur[2]=5,化为二进制就是1 0 1.结合函数flag(),如果出现0发生变化的情况,比如:110=6，6&5>0.*/}}//for(int i=1;i<=n;i++) cout<<cur[i]<<" ";for(int i=0;i<top;i++)if(flag(state[i],1)) dp[1][i]=1;for(int i=2;i<=n;i++){///从第2行开始for(int j=0;j<top;j++)///枚举第i行所有的情况{if(!flag(state[j],i)) continue;for(int k=0;k<top;k++)///枚举第i-1行所有的情况{if(!flag(state[k],i-1)) continue;if((state[j]&state[k])) continue;///若满足上下1与1不相邻的情况dp[i][j]=(dp[i][j]+dp[i-1][k])%mod;/// cout<<dp[i][j]<<" ";}}}int ans=0;for(int i=0;i<top;i++)ans=(ans+dp[n][i])%mod;cout<<ans<<endl;return 0;
}