P1879

一直看不出来哪里有错误，60pts,WA #2#4#6#9

思路都在注释里，孩子交了好几发已经不会了

#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}
inline void write(int x)
{
    if(x<0) x=-x,putchar('-');
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
/*-----------------------OI使我快乐---------------------------*/
const int  mod = 100000000;
int n,m;
int ok[15][15];
int F[15];
int f[15][16200];//行数为i，状态为j的方案数
int s[3][16200],cnt[3],tot;//滚动数组保存上一行和这一行的可行状态
void dfs(int nn,int opt)
{
    cnt[opt]=0;
    memset(s[opt],0,sizeof(s[opt]));
    for(int i = 0;i < (1 << m);++i)//枚举这行所有可能状态
    {
        if((F[nn] | i) > F[nn]) continue;//保证原数组0位置上没数
        if((i & (i << 1)) || (i & (i >> 1))) continue;//保证此状态没有相邻的草地
        s[opt][++cnt[opt]] = i;//存储这个可行状态
    //    cout<<i<<endl;
    }
    //cout<<"-------"<<endl;
}
void DP()
{
    dfs(1,1 % 2);//第一行所有的可行状态找出来
    for(int i = 1;i <= cnt[1 % 2];++i)
        f[1][s[1 % 2][i]] = 1;//第一行所有可行状态的方案数为1
    for(int i=2;i<=n;++i)//从第二行开始枚举
    {
        dfs(i,i % 2);//找出第i行可行状态
        for(int j = 1;j <= cnt[i % 2];++j)//枚举第i行可行状态
        {
            for(int k = 1;k <= cnt[!(i % 2)];++k)//枚举i-1行可行状态
            {
                //if((((s[i % 2][j] << 1) & s[!(i % 2)][k])) && (!((s[i % 2][j]>>1) & s[!(i % 2)][k])))//两个方案不冲突
                if((s[i % 2][j] & s[!(i % 2)][k]) == 0)//上下不相邻,即相同位置上不都是1
                {
                    //cout<<s[i % 2][j]<<" "<<s[!(i % 2)][k]<<endl;
                    f[i][s[i % 2][j]] = (f[i][s[i % 2][j]] + f[i - 1][s[!(i % 2)][k]] % mod) % mod;//方案数转移
                }
            }
        }
    }
}
signed main()
{
    n=read(),m=read();
    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j)
        {
            ok[i][j]=read();
            F[i]=(F[i] << 1) + ok[i][j];//将每行的土地情况压缩
        }
    DP();
    int final_ans=0;
    for(int i=0;i<(1<<n);++i)
    {
        final_ans=(final_ans+f[n][i]%mod)%mod;//将最后一行的所有结果汇总
    }
    write(final_ans % mod);
    cout<<endl;
    system("pause");
    return 0;
}