注意g[N]的处理方法
先取反相加，然后再与状态按位与如果有两个1，就说明该状态不合法

#include <iostream>
#include <vector>

using namespace std;
int n,m;
const int N=14,M=1<<12;
const int mod=1e8;
vector<int> state;
vector<int> head[M];
int f[N][M];
int g[N];

int check(int x)
{
    for(int i=0;i<m;i++)
    {
        if((x>>i&1)&&(x>>i+1&1))
        return 0;
    }
    return 1;

}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<m;j++)
        {
            int t;
            cin>>t;
            g[i]+=!t<<j; 
        }
    }

    for(int i=0;i<1<<m;i++)
    {
        if(check(i))
        state.push_back(i);
    }
    for(int i=0;i<state.size();i++)
    {
        for(int j=0;j<state.size();j++)
        {
            int a=state[i],b=state[j];
            if((a&b)==0)
            head[i].push_back(j);
        }
    }
    f[0][0]=1;
    for(int i=1;i<=n+1;i++)
    {
        for(int a=0;a<state.size();a++)
        {
            for(int b=0;b<head[a].size();b++)
            {
                int t=head[a][b];
                if(g[i]&state[a])
                continue;
                f[i][a]=(f[i][a]+f[i-1][t])%mod;
            }
        }
    }
    cout<<f[n+1][0];

}

二刷

注意在进行dp时，先遍历行数，再遍历状态，再遍历可转移到他的状态(相当于二重循环，先遍历状态a，再遍历可转移到a的状态b)

#include <iostream>
#include <vector>
#include <cstring>

using namespace std;
const int N=15;
const int M=1<<15;
const int mod=1e8;
int f[N][M];
int g[N];
int n,m;
vector<int> state;
vector<int> head[M];

int check(int a)
{
    for(int i=0;i<m;i++)
    {
        if((a>>i&1)&&(a>>i+1&1))
            return 0;
    }
    return 1;
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<m;j++)
        {
            int t;
            cin>>t;
            g[i]+=!t<<j;
        }
    }
    for(int i=0;i<1<<m;i++)
    {
        if(check(i))
        {
            state.push_back(i);
        }
    }
    for(int i=0;i<state.size();i++)
    {
        for(int j=0;j<state.size();j++)
        {
            int a=state[i];
            int b=state[j];
            if(a&b) continue;
            head[i].push_back(j);
        }
    }
    f[0][0]=1;
    for(int i=1;i<=n+1;i++)
    {
        for(int a=0;a<state.size();a++)
        {
            for(int b=0;b<head[a].size();b++)
            {
                int t=head[a][b];
                if(g[i]&state[a]) continue;
                f[i][a]=(f[i][a]+f[i-1][t])%mod;
            }
        }
    }
    cout<<f[n+1][0];

    return 0;

}

三刷

有几个坑
1. 注意check里面是遍历到m(状态按列遍历)

#include <iostream>
#include <cstring>
#include <vector>

using namespace std;

const int N=1<<15;
long long f[15][N];
int g[13][13];
int n,m;
vector<int> state;
vector<int> head[N];
const int mod=1e8;

int check(int x)
{
    for(int i=0;i<=m-1;i++)
    {
        if((x>>i) & (x>>i+1) &1)
        {
            return 0;
        }
    }
    return 1;
}

int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>g[i][j];
        }
    }
    for(int i=0;i<1<<m;i++)
    {
        if(check(i)) state.push_back(i);
    }

    for(int i=0;i<state.size();i++)
    {
        for(int j=0;j<state.size();j++)
        {
            int a=state[i];
            int b=state[j];
            if((a&b)==0)
            {
                head[i].push_back(j);
            }
        }
    }
    f[0][0]=1;
    int flag;
    for(int i=1;i<=n+1;i++)
    {
        for(int k=0;k<state.size();k++)
        {
            int a=state[k];
            for(int j=0;j<=m-1;j++)
            {
                if(g[i][m-j]==0 && ((a>>j)&1))
                {
                    flag=1;
                    break;
                }
                flag=0;
            }
            if(flag==0)
            {   
                for(auto t : head[k])
                {
                    int b=state[t];
                    f[i][k]=(f[i][k]+f[i-1][t])%mod;
                }
            }
        }
    }
    cout<<f[n+1][0];
    return 0;
}

总结

做一个小总结：
状态压缩dp在做dp时：
第一层循环为遍历到第几行，一般遍历到n+1，方便计算方案数
第二层循环若无其他限制（如小国王中数量的限制）则遍历状态，代表第i行为第k个状态时的方案
第三层循环为遍历可转移到第k个状态的状态，因此可以理解head[k]中存的是可转移到状态k的状态，此层循环含义为：第i行为状态k了，那么第i-1行可以为head[k]里的状态

初始化一般为f[0][0][0]=1;