SRM523 Div2 Hard

1000
頑張ってメモ化する。

const int T = (1 << 10) + 1;
const int D = 10 + 1;
int t[D][T];

const int mod = 1000000007;

const int B = 1048576 + 1;
string b[B];
int b_size;

inline
int rec(int depth, int bit, int H, int W)
{
  if (depth == H) return 1;
  if (t[depth][bit] != -1) {
    return t[depth][bit];
  }
  int sum = 1;

  for (int i = 0; i < b_size; ++i) {
    bool flg = true;
    int next = 0;
    for (int j = 0; j < W && flg; ++j) {
      int s = 1 << (j + 0);
      int t = 1 << (j + 1);
      int u = 1 << (j + 2);
      if (b[i][j] == '.') {
        continue;
      } else if (b[i][j] == 'A') {
        flg = flg && (bit & s) && (j + 0 < W);
        next |= s;
        j += 0;
      } else if (b[i][j] == 'B') {
        flg = flg && (bit & s) && (bit & t) && (j + 1 < W);
        next |= s | t;
        j += 1;
      } else if (b[i][j] == 'C') {
        flg = flg && (bit & s) && (bit & u) && (j + 2 < W);
        next |= s | t | u;
        j += 2;
      } else ;
    }
    if (flg) {
      sum += rec(depth + 1, next, H, W);
      sum %= mod;
    }
  }

  return t[depth][bit] = sum;
}

inline
void build(string s, int L)
{
  if (s.size() == L) {
    if (s != string(L, '.')) b[b_size++] = s;
  }
  if (L <= s.size()) return;
  build(s + ".", L);
  build(s + "A", L);
  build(s + "BB", L);
  build(s + "CCC", L);
}

class SmallBricks31 {
public:
  int countWays(int w, int h) 
  {
    b_size = 0;
    build("", w);
    fill(&t[0][0], &t[D-1][T], -1);

    return rec(0, (1 << (w+1)) - 1, h, w);
  }

};