NC15034 德玛西亚万岁

题目地址：

https://ac.nowcoder.com/acm/problem/15034

基本思路：

我们发现 $n,m$ 非常小，基本上就能确定是一个状压 $dp$ ，那么其实很明显我们考虑上下两层之间的转移。然后我们要做几个判定，在枚举当前行状态时首先当前行的状态不能和地图起冲突，其次也不能出现站位相邻的情况，然后在上下两行枚举时也要注意不能出现上下相邻的情况。以上这几种情况可以使用位运算技巧轻松判断，那么我们就能得到在去掉这些不符的情况后的转移方程为： $dp[i][state] = \sum_{} dp[i-1][state]$ 。那么注意一些位运算技巧，并且根据这些条件转移最后统计最后一层的所有状态就能得到答案。注意一下多组输入。

参考代码：

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
#define IO std::ios::sync_with_stdio(false)
#define int long long
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, l, r) for (int i = l; i >= r; i--)
#define mset(s, _) memset(s, _, sizeof(s))
#define pb push_back
#define pii pair <int, int>
#define mp(a, b) make_pair(a, b)
#define INF (int)1e18

inline int read() {
  int x = 0, neg = 1; char op = getchar();
  while (!isdigit(op)) { if (op == '-') neg = -1; op = getchar(); }
  while (isdigit(op)) { x = 10 * x + op - '0'; op = getchar(); }
  return neg * x;
}
inline void print(int x) {
  if (x < 0) { putchar('-'); x = -x; }
  if (x >= 10) print(x / 10);
  putchar(x % 10 + '0');
}

const int mod = 100000000;
int n,m,x,a[15];
int dp[15][1 << 13];
signed main() {
  IO;
  while (cin >> n >> m) {
    rep(i, 0, n - 1) {
      a[i] = 0;
      rep(j, 0, m - 1) {
        cin >> x; a[i] = (a[i] << 1) + x;//将地图每一行压成状态;
      }
    }
    mset(dp, 0);
    for (int i = 0; i < n; i++) {
      for (int p = 0; p < (1 << m); p++) {
        if ((p & a[i]) != p) continue; //判断是不是会和地图冲突;
        if (p & (p >> 1)) continue;//判断相邻之间会不会冲突;
        if (i == 0) dp[i][p] = 1;//第一行因为没有上一行了，所以自身不冲突就行;
        else {
          for (int q = 0; q < (1 << m); q++) {
            if (p & q) continue;//判断上下两行是否冲突;
            dp[i][p] = (dp[i][p] + dp[i - 1][q]) % mod;//不冲突那么相加，注意取模;
          }
        }
      }
    }
    int ans = 0;
    //统计最后一行的所有转态;
    for (int i = 0; i < (1 << m); i++) ans = (ans + dp[n - 1][i]) % mod;
    cout << ans << '\n';
  }
  return 0;
}