德玛西亚万岁

题意：
有n∗m的01矩阵
1表示可以放置一个英雄，0表示不能
任意两个英雄不能相邻放置
问总共有多少种方案数,mod 1e8
思路：
1.，这么小的数据可以想到dfs去写，但是看到要取模就知道尽管能剪枝，但情况还是很多，会超时。
2.对于每个位置只有放英雄和不放英雄两种状态，所以可以直接考虑二进制，用01串状态压缩。
3.取第i行的状态，st某二进制位上为1表示选某一列，为0表示不选。
4.将每一行的输入取反，并变成01串a[i]。
5.每一列的状态st，显然是不服合要求的，即左右的位置不能有士兵、只有输入是1的位置才能放士兵。
6.取第i-1行的状态，显然是不服合要求的，即和上一行的士兵不能相邻。
7.转移方程就是
8.显然答案是：

ll ans=0;
for(int i=0;i<cnt;i++) ans=(ans+dp[n][i])%mod;
cout<<ans<<endl;

9.注意一下多组输入（还要开long long吧），同时要初始化两个数组，不然只能过10%。
Code：

#include<bits/stdc++.h>
#define js ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
typedef long long ll;
const int mod=100000000;
int n,m;
ll dp[15][1<<12],a[15];
int main() {
    js;
    while(cin>>n>>m) {
        memset(dp,0,sizeof(dp));
        memset(a,0,sizeof(a));
        for(int i=1;i<=n;++i)
        for(int j=0;j<m;++j) {
        int tmp; cin>>tmp;
            tmp^=1;
            a[i]|=(tmp<<j);
        }
        dp[0][0]=1; int cnt=1<<m;
        for(int i=1;i<=n;++i)
        for(int st=0;st<cnt;++st) {
            if(st&(st>>1)||st&a[i]) continue;
            for(int st1=0;st1<cnt;++st1) {
                if(st&st1) continue;
                dp[i][st]=(dp[i][st]+dp[i-1][st1])%mod;
            }
        }
        ll ans=0;
        for(int i=0;i<cnt;i++)ans=(ans+dp[n][i])%mod;
        cout<<ans<<endl;
    }
    return 0;
}