2020 -6

6-3 德玛西亚万岁

状压dp板子。。。

#include <bits/stdc++.h>
using namespace std;
const int mod = 100000000;
int n, m;
int a[15][15];
int b[13][1<<12];
int ans[13][1<<12];
int f(int i, int j){           //f(i, j) 表示第i行为状态j时，不合法时输出-1
    for (int k=1;k<=m;k++)  if (!a[i][k] && ((j>>(m-k))&1))    return -1;
    for (int k=1;k<=m;k++)  if (((j>>(m-k))&1) && ((j>>(m-k+1))&1))   return -1;
    return 0;
}
int main(){
    while (cin >> n >> m){
        memset (ans, 0, sizeof ans);
        int res = 0;
        for (int i=1;i<=n;i++)  for (int j=1;j<=m;j++)
            cin >> a[i][j];
        for (int i=1;i<=n;i++)    for (int j=0;j<(1<<m);j++)
            b[i][j] = f(i, j);
        for (int j=0;j<(1<<m);j++)  if (b[1][j]!=-1)
            ans[1][j] = 1;
        for (int i=2;i<=n;i++)    for (int j=0;j<(1<<m);j++)    if (b[i][j]!=-1){
            for (int k=0;k<(1<<m);k++)  if (b[i-1][k]!=-1){
                if (j&k)    continue;
                ans[i][j] = (ans[i][j]+ans[i-1][k])%mod;
            }
        }
        for (int j=0;j<(1<<m);j++)
            res = (res+ans[n][j])%mod;
        cout << res << endl;
    }
    return 0;
}