「校内训练2019-10-04」魔法女孩

Solution

$1..9$内一共有$4$个偶数和$5$个奇数,而在统计奇数和偶数的情况下,只有这两种情况。
我们就从左上角开始每$n\times m$个方格当做一个矩形,可以得到每一个矩形的相对相同的位置的奇偶性必须是相同的。
问题就变成了有多少种情况满足$n\times m$矩阵的每一行和每一列的奇偶性相同。
定义$f[i][j]$表示我们当前在$i$行,第$i$行的奇偶状态为$j$的方案数。
那么考虑$f[i][j]$转移到$f[i+1][j^s]$,这个$s$表示的就是第$i+1$行奇偶性的方案,那么$s$必须满足如果有固定的奇偶性,那么就要固定为$0..1$,否则可以随意,而且满足本身的$1$的个数为奇数个。
初始状态为$f[0][0]=1$。
答案为$f[n][2^m-1]$。

Code

#include <bits/stdc++.h>
#define lowbit(x) (x & -x) 
using namespace std;
typedef long long ll;
const int MOD = 1e9 + 7;
const int N = 55;
int h, w, n, m;
char s[N];
int a[N][N], cnt[15][15];
int pw4[2505], pw5[2505];
ll f[15][1 << 12];
template <typename T> void pls(T& x, T y) {
  x += y;
  if (x >= MOD) x -= MOD;
}
int bitCount(int sta) {
  int res = 0;
  for (int i = sta; i; i -= lowbit(i)) res++;
  return res;
}
int main() {
  pw4[0] = pw5[0] = 1;
  for (int i = 1; i <= 2500; i++) 
    pw4[i] = 1ll * pw4[i - 1] * 4 % MOD, pw5[i] = 1ll * pw5[i - 1] * 5 % MOD;
  scanf("%d%d%d%d", &h, &w, &n, &m);
  for (int i = 1; i <= h; i++) {
    scanf("%s", s);
    for (int j = 0; j < w; j++) {
      if (s[j] == '.') a[i][j] = -1;
      else a[i][j] = (s[j] - '0') & 1;
    }
  }
  memset(cnt, 0, sizeof cnt);
  for (int i = 1; i <= n; i++) {
    for (int j = 0; j < m; j++) {
      for (int i1 = i; i1 <= h; i1 += n) {
        for (int j1 = j; j1 < w; j1 += m) {
          if (a[i1][j1] == -1) cnt[i][j]++;
          if (a[i][j] == -1 && a[i1][j1] != -1) a[i][j] = a[i1][j1];
          if (a[i][j] != -1 && a[i1][j1] == -1) continue;
          if (a[i][j] != -1 && a[i1][j1] != -1) {
            if (a[i][j] != a[i1][j1]) {
              printf("0\n");
              return 0; 
            } else continue;
          }
        }
      }
    }
  }
  f[0][0] = 1;
  for (int i = 0; i < n; i++) {
    for (int msk = 0; msk < (1 << m); msk++) {
      if (f[i][msk] == 0) continue;
      for (int sta = 0; sta < (1 << m); sta++) {
        if (bitCount(sta) % 2 == 0) continue;
        bool isok = 1;
        for (int j = 0; j < m; j++) {
          if (a[i + 1][j] != -1 && a[i + 1][j] != (sta >> j & 1)) {
            isok = 0;
            break;
          }
        }
        if (!isok) continue;
        int cnt0 = 0, cnt1 = 0;
        for (int j = 0; j < m; j++) {
          if (sta >> j & 1) cnt1 = (cnt1 + cnt[i + 1][j]) % MOD;
          else cnt0 = (cnt0 + cnt[i + 1][j]) % MOD;
        }
        pls(f[i + 1][msk ^ sta], 1ll * f[i][msk] * pw4[cnt0] % MOD * pw5[cnt1] % MOD); 
      }
    }
  }
  printf("%lld\n", f[n][(1 << m) - 1]);
  return 0;  
}
最后修改:2019 年 10 月 04 日 10 : 35 PM
如果觉得我的文章对你有用,请随意赞赏

发表评论