$\huge \color{orange}{成魔之路->}$ $\huge \color{purple}{算法提高课题解}$

思路：

• $1. 状态表示$
  $集合：前\ i\ 行已经摆好，且第\ i\ 行状态是\ a\ 的方案$
  $属性：Count$

• $2. 状态转移$
  $a\ 是第\ i\ 行的状态，b\ 是第\ {i-1}\ 行的状态，b\ 是\ a\ 所能转移的状态$
  $f[i][a]\ +=f[i-1][b]$

可参考： 小国王

完整代码

#include<bits/stdc++.h>

using namespace std;

const int N = 14, M = 1 << 12, mod = 1e8;

int n,m;
int g[N];
int f[N][M];
vector<int> state;
vector<int> head[M];

//如果有相邻的1，则不合法
bool check(int state)
{
    return !(state&state>>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)) head[a].push_back(b);
        }

    f[0][0]=1;    
    for(int i=1;i<=n+1;i++) //枚举每一行
        for(auto a : state) //枚举所有状态
            if(!(g[i]&a)) //该行状态是否与枚举的状态冲突
                for(auto b : head[a]) //枚举前一行状态，且是该行状态能够转移到的状态
                    f[i][a]=(f[i][a]+f[i-1][b])%mod; //状态 b 转移到状态 a

    cout<<f[n+1][0]<<endl; //不需要枚举第n行的所有符合的方案了

    return 0;
}