德玛西亚万岁（状压dp）

题目：

给一个n*m的01矩阵。1代表可以安放士兵，0代表不能。士兵不能安放在相邻的位置（上下左右）。问有多少种安防士兵的方案。答案对1e8取模。n，m最大12

做法：

看n，m的数据范围，这是状压的数据范围。
题目只问士兵的方案数，没有限制士兵的数量。所以我们直接对每一行的状态进行枚举，一行一行转移。
对于第i行的状态sta，首先要与这行可放置士兵的状态无冲突。即sta中1的位，在给的01矩阵中都是1，即sta&b[i] == sta。然后这一行相邻位置不能同时有1。这样处理：sta&(sta<<1) == 0。经过这两个判断，这一行这种状态才合法。然后就是枚举上一行所有不与sta冲突的状态pre来转移。dp[i][sta] += dp[i-1][pre];
当然不要忘记取mod。

代码：

#include <bits/stdc++.h>
#define debug(a) cout << #a ": " << a << endl
#define IOS ios::sync_with_stdio(false), cin.tie(0)
using namespace std;
typedef long long ll;
const int mod = 1e8;
const int N = 13;
int n, m, a[N][N], b[N], dp[N][1<<N];
int main(void){    
    IOS;
    int n, m;
    while (cin >> n >> m){
        for (int i = 1; i <= n; ++i){
            b[i] = 0;
            for (int j = 1; j <= m; ++j){
                cin >> a[i][j];
                b[i] |= (a[i][j]<<(j-1));
            }
        }
        memset(dp, 0, sizeof dp);
        dp[0][0] = 1;
        for (int i = 1; i <= n; ++i){
            for (int j = 0; j < (1<<m); ++j){
                if ((b[i]&j) != j) continue;
                if (j&(j<<1)) continue;
                for (int k = 0; k < (1<<m); ++k){
                    if (k&j) continue;
                    (dp[i][j]+=dp[i-1][k]) %= mod;
                }
            }
        }
        int ans = 0;
        for (int i = 0; i < (1<<m); ++i){
            (ans += dp[n][i]) %= mod;
        }
        cout << ans << endl;
    }
    return 0;
}