装压DP模板题

做法

设为第行状态为时的方案数量， , 答案为

CODE

#include <algorithm>
#include <cctype>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstring>
#include <deque>
#include <functional>
#include <list>
#include <map>
#include <iomanip>
#include <iostream>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;
#define int long long
#define I inline
#define ri register int
#define lowbit(x) x & -x
#define For(i , x , y) for(ri i = x ; i <= y ; ++ i)
#define Next(i , x) for(ri i = head[x] ; i ; i = e[i].nxt)
I int read() {
    int s = 0 , w = 1; char ch = getchar();
    while(ch < 48 || ch > 57) {if(ch == '-') w = -1; ch = getchar();}
    while(ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48) , ch = getchar();
    return s * w;
}
const int P = 100000000;

int n , m , tot , a[13] , f[13][1 << 12] , state[1 << 12];

I bool judge(int x , int y) {
    For(i , 0 , m - 1)    if( !((x >> i) & 1 ) && ((y >> i) & 1)) return 0;
    return 1;
}
signed main() {
    while(scanf("%d%d",&n,&m) != EOF) {
        memset(a , 0 , sizeof(a));
        memset(f , 0 , sizeof(f)) ; 
        tot = 0;
        For(i , 1 , n) 
            For(j , 1 , m) {    
                int x = read() ; 
                a[i] = ( a[i] << 1 ) | x; 
            }

        For(i , 0 , (1 << m) - 1)
            if( !( i & (i >> 1) ) ) state[++ tot] = i;
    //    For(i , 1 , n) printf("%d**\n" , a[i] ^ state) ; 
        For(i , 1 , tot) f[1][state[i]] = 1;

        For(i , 2 , n)
            For(j , 1 , tot)
                if(judge(a[i - 1] , state[j])) {
                //    puts("*");
                    For(k , 1 , tot)
                        if(judge(a[i] , state[k]))
                            if( ! (state[j] & state[k]) ) (f[i][state[k]] += f[i - 1][state[j]] ) %= P; 
                }
        int Ans = 0;
        For(i , 1 , tot) (Ans += f[n][state[i]]) %= P;
        cout << Ans << endl;
    }
    return 0;
}