[每日一题] [NC15034] 德玛西亚万岁

题目大意：有一些人可以站在mxn的格子里面，有一些格子不能站人，不能站在相邻格子，有几种站法。

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

这题就是一道很基本的状态压缩DP，时间复杂度是O(m2^n2^n)对于m=n=12刚好不会TLE。
一开始没注意审题，注意支持多组数据。

ll doit(int n, int m, VI& grid) {
  int mask_size = (1 << m);
  VVL dp(n + 1, VL(mask_size, 0));
  dp[0][0] = 1;
  for (int row = 0; row < n; ++row) {
    int now = row + 1;
    int prev = row;
    for (int new_mask = 0; new_mask < mask_size; ++new_mask) {
      if (new_mask & (new_mask >> 1)) continue;
      bool fine = true;
      REP(j, m) {
        if (new_mask & (1 << j)) {
          if ((grid[row] & (1 << j)) == 0) {
            fine = false;
          }
        }
      }
      if (!fine) continue;
      for (int old_mask = 0; old_mask < mask_size; ++old_mask) {
        if (old_mask & new_mask) continue;
        dp[now][new_mask] += dp[prev][old_mask];
        dp[now][new_mask] %= MOD;
      }
    }
  }
  ll ans = 0;
  REP(i, mask_size) {
    ans += dp[n][i];
    ans %= MOD;
  }
  return ans;
}

int main(int argc, char* argv[]) {
  /* Do not use for codejam. */
  /* ios_base::sync_with_stdio(false); cin.tie(NULL); */
  int n, m;
  while (scanf("%d%d",&n,&m) == 2) {
    VI grid(n, 0);
    REP(i,n){
      REP(j,m){
        readint(curr);
        grid[i] = grid[i] * 2 + curr;
      }
    }
    printlong(doit(n,m,grid));
  }
  return 0;
}