E26 状态压缩DP 玉米田

#include <cstdio>
#include <vector>
using namespace std;
const int N=14, M=1<<N, mod=100000000;
int g[N], f[N][M];
vector<int> st, last[M];
int main(){
    int n, m; scanf("%d%d", &n, &m);
    for(int i=1; i<=n; ++i)
        for(int j=0, x; j<m; ++j)
            scanf("%d", &x), g[i] |= !x << j;
    for(int x=0; x<1<<m; ++x)
        if(!(x & x << 1)) st.push_back(x);
    for(int x : st) for(int y : st)
        if(!(x & y)) last[x].push_back(y);
    f[0][0] = 1;
    for(int i=1; i<=n+1; ++i)
        for(int x : st){
            if(x & g[i]) continue;
            for(int p : last[x]) f[i][x] = (f[i][x] + f[i-1][p]) % mod;
        }
    printf("%d\n", f[n+1][0]);
    return 0;
}