每日一题 6月3日 德玛西亚万岁 每行状态的状压DP

题目链接：https://ac.nowcoder.com/acm/problem/15034
题目大意：

#include <bits/stdc++.h>
#define LL long long
using namespace std;

vector<int> v[15];
int pos[15];
LL f[15][1<<13];
const int mod=100000000;
void DFS(int tot, int i, int m, int s, int p){
    if(i>m){
        v[tot].push_back(s);
        return ;
    }
    if(pos[i]==0){
        DFS(tot, i+1, m, s*2, 0);
    }
    else{
        DFS(tot, i+1, m, s*2, 0);
        if(!p){
            DFS(tot, i+1, m, s*2+1, 1);
        }
    }
}

int main(){

    int n, m;
    while(~scanf("%d%d", &n, &m)){
        memset(f, 0, sizeof(f));
        for(int i=1; i<=n; i++){//预处理每行的合法状态
            v[i].clear();
            for(int j=1; j<=m; j++){
                scanf("%d", &pos[j]);
            }
            DFS(i, 1, m, 0, 0);
        }
        for(auto x: v[1]){
            f[1][x]=1;
        }
        for(int i=2; i<=n; i++){
            for(auto x: v[i]){
                for(auto y: v[i-1]){
                    if((x&y)==0){//如果i和i-1不冲突就可以转移
                        f[i][x]+=f[i-1][y]; f[i][x]%=mod;
                    }
                }
            }
        }
        LL ans=0;
        for(auto x: v[n]){
            ans+=f[n][x]; ans%=mod;
        }
        printf("%lld\n", ans);
    }

    return 0;
}