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;
}

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;
}