状态压缩 dp

a & b == 0
a | b 不能有相邻的 1
j >= cnt[a]
dp[i][j][a] += dp[i - 1][j - cnt[a]][b];
10 * 100 * 1000 * 1000 = 1e9

// 状态压缩dp

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 12, M = 1 << 10, K = 110;

int n, m;
vector<int> state;
int id[M], cnt[M];
vector<int> head[M];
LL f[N][K][M];


bool check(int state){
    for(int i = 0;i < n;i ++ )
        if((state >> i & 1) && ((state >> i + 1 & 1)))
            return false;
    return true;
}

int count(int state){
    int res = 0;
    while(state){
        res += state & 1;
        state >>= 1;
    }
    return res;
}

int main(){

    scanf("%d%d", &n, &m);
    for(int i = 0;i < 1 << n;i ++ ){
        if(check(i)) state.push_back(i);
        cnt[i] = count(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 && check(a | b))
                head[a].push_back(b);
        }

    f[0][0][0] = 1;
    for(int i = 1;i <= n + 1;i ++ )
        for(int j = 0;j <= m;j ++ )
            for(int a = 0;a < state.size();a ++ )
                for(int &b : head[state[a]]){
                    int c = cnt[state[a]];
                    if(c <= j) f[i][j][state[a]] += f[i - 1][j - c][b];
                }

    printf("%lld\n", f[n + 1][m][0]);

    return 0;
}

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>

using namespace std;

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

// a & b == 0
// a 和 b 不能包含相邻的 1
// f[i][a] += f[i - 1][b]

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

bool check(int state){
    for(int i = 0;i < n;i ++ )
        if((state >> i & 1) && (state >> i + 1 & 1))
            return false;
    return true;
}

int main(){

    scanf("%d%d", &n, &m);
    for(int i = 1;i <= n;i ++ ) 
        for(int j = 0;j < m;j ++ ){
            int x; cin >> x;
            g[i] += !x << 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);
        }
    for(int i = 1;i <= n + 1;i ++ )
        for(int a = 0;a < state.size();a ++ )
            for(int &b : head[a]){
                if(g[i] & state[a]) continue;
                f[i][a] += f[i - 1][b];
            }

    printf("%d\n", f[n + 1][0]);

    return 0;
}