没什么可说的，入门级状压DP，直接撸掉

#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <map>
#include <queue>
#include <stack>
#include <set>
#define LL long long
#define FOR(i, x, y) for(int i=x;i<=y;i++)
using namespace std;
const int maxn = 5000;
const int MOD = 100000000;
int N, M, K;
int C[20], state[maxn];
int dp[20][maxn];
bool judge(int x)
{
    if(x & (x << 1)) return false;
    return true;
}
void init()
{
    memset(dp, 0, sizeof(dp));
    memset(state, 0, sizeof(state));
    memset(C, 0, sizeof(C));
    int r = (1 << M) - 1; K = 0;
    FOR(i, 0, r) if(judge(i)) state[++K] = i;
}
int main()
{
    while(scanf("%d %d", &N, &M)!=EOF)
    {
        init();
        int X;
        FOR(i, 1, N)
        FOR(j, 1, M)
        {
            scanf("%d", &X);
            if(X == 0) C[i] = C[i] | (1 << (M - j));
        }
        FOR(i, 1, K)
        {
            if(!(state[i] & C[1])) dp[1][i] = 1;
        }

        FOR(i, 2, N)
        FOR(j, 1, K)
        {
            if(C[i-1] & state[j]) continue;
            FOR(l, 1, K)
            {
                if((C[i] & state[l]) || (state[l] & state[j])) continue;
                dp[i][l] = (dp[i-1][j] + dp[i][l]) % MOD;
            }
        }
        int ans = 0;
        FOR(i, 1, K) ans = (ans + dp[N][i]) % MOD;
        printf("%d\n", ans);
    }
    return 0;
}

POJ 3254 简单状压DP