SRM532 Div2 Hard

950
メモ化する。
memo[何行目][n番目のマスの状態]
マスの状態は3進数表現で "自身が1で下に1が必要" or "自身が1で下に0が必要" or "自身が0"

const lli mod = 1000000007;
const int H = 100 + 1;
const int BIT = 6561 + 1;
lli memo[H][BIT];

bool valid(int bit)
{
  while (bit) {
    if (bit % 3 == 2) return false;
    bit /= 3;
  }
  return true;
}

lli rec(int h, int w, int bit)
{
  if (memo[h][bit] != -1) return memo[h][bit];
  if (h == 0) return memo[h][bit] = valid(bit);
  
  int n = 0, m = 0;
  int b = bit;
  for (int i = 0; i < w; ++i) {
    int t = b % 3;
    if (t) n += (1 << i);
    if (t == 2) m += (1 << i);
    b /= 3;
  }
  
  lli sum = 0;
  for (int next = 0; next < (1 << w); ++next) {
    if ((m & next) == m) ; else continue;    

    bool flg = true;
    for (int i = 0; i < w; ++i) {
      int b = 1 << i;
      if ((next & b) && (n & b) && !(m & b)) flg = false;
    }
    if (!flg) continue;

    int x = 0;
    for (int i = 0; i + 1 < w; ++i) {
      if (next & (1 << i)) x ^= 1 << (i + 1);
    }
    for (int i = 1; i < w; ++i) {
      if (next & (1 << i)) x ^= 1 << (i - 1);
    }
    for (int i = 0; i < w; ++i) {
      x ^= n & (1 << i);      
    }
    x &= next;    

    int y = 0;
    int p3 = 1;
    for (int i = 0; i < w; ++i) {
      if (x & (1 << i)) y += 2 * p3;
      else if (next & (1 << i)) y += p3; 
      p3 *= 3;
    }

    sum += rec(h - 1, w, y);
    sum %= mod;
  }

  return memo[h][bit] = sum;
}

class DengklekPaintingSquares {
public:
  int numSolutions(int h, int w) 
  {
    fill(&memo[0][0], &memo[H - 1][BIT], -1);
    return rec(h, w, 0);
  }

};