SRM532 Div1 Medium

450
とりあえずメモ化する。
memo[着目してる頂点][Kコ前までの頂点の状態][何コ前と辺を付けるか][残りの辺]
Kコ前の頂点たちは、次数が偶数か奇数がを覚えておけばいい。k <= 8 なので、ビットで持つ。
"K前の頂点のどれかと辺をいくつか付ける" or "次の頂点に進む"
本番中にデバッグしきれなかった。ビットを使うときって、どうもデバッグが上手く行かない気がする。

const int BIT = (1 << 9) + 1;
const int NODE = 30 + 1;
const int EDGE = 30 + 1;
const int NTH = 9;
lli t[NODE][BIT][NTH][EDGE];

const lli mod = 1000000007;

int N, M, K;

lli rec(int node, int bit, int nth, int edge)
{
  if (node == N) return 0;
  if (edge == 0) return bit == 0;
  if (t[node][bit][nth][edge] != -1) return t[node][bit][nth][edge];

  lli sum = 0;

  if (nth < min(node, K)) {
    for (int i = 0; i <= edge; ++i) {
      int next = i % 2 ? bit ^ (1 << (nth + 1)) ^ 1 : bit;
      sum += rec(node, next, nth + 1, edge - i);
      sum %= mod;
    }
  } else {
    if (bit & (1 << K)) ; else {
      int mask = (1 << (K + 1)) - 1;
      sum = rec(node + 1, (bit << 1) & mask, 0, edge);
    }
  }

  return t[node][bit][nth][edge] = sum;
}

class DengklekBuildingRoads {
public:
  int numWays(int N_, int M_, int K_)
  {
    N = N_;
    M = M_;
    K = K_;
    fill(&t[0][0][0][0], &t[NODE - 1][BIT - 1][NTH - 1][EDGE], -1);

    return rec(0, 0, 0, M);
  }

};