前言:

好简单啊...我最近写这种题跟写x x题一样...或许就是x x题吧...

思路:

令f[i][j]表示第i行状态时j的方案数,然后把合法的转移一下,不合法的不转移就好了.至从我码力变好了之后写这种题真的...)

代码:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=13,M=(1<<13);
const int mod=100000000;
int f[N][M];//到了第i行,站人的状态为j的方案数. 
int mp[N];
int n,m,x;
bool ck(int u)
{
    bool last=false;
    for(int i=0;i<m;i++)
    {
        if(last&&(u>>i&1))    return true;
        else if(u>>i&1)        last=true;
        else                last=false;
    }return false;
}
int main()
{
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        memset(mp,0,sizeof mp);
        memset(f,0,sizeof f);
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                scanf("%d",&x);
                mp[i]*=2;
                mp[i]+=x;
            }
        }f[0][0]=1;int ans=0;
        for(int i=1;i<=n;i++)
        {
            for(int j=0;j<(1<<m);j++)//枚举这行站人的情况.
            {
                if(ck(j)||((j|mp[i])!=mp[i]))    continue;
                for(int k=0;k<(1<<m);k++)//枚举上行站人的情况. 
                {
                    if(j&k)    continue;
                    f[i][j]+=f[i-1][k];
                    f[i][j]%=mod;
                }
            } 
        }
        for(int i=0;i<(1<<m);i++)
        {
            ans+=f[n][i];ans%=mod;
        }printf("%d\n",ans);
    }
    return 0;
}