SRM 554 Div2 Hard TheBrickTowerHardDivTwo

問題

C種類の色のブロック（1x1x1のサイズ）が各色無尽蔵にあり、これらのブロックを積み上げていき、2x2xHのタワーを作りたい。隣接するブロックが同色であるというのををK個以下に抑えるようにタワーを作る方法は何通りあるか。1234567891で割った余りを返せ。

やりかた

Editorial、Practice room を参考にしました。

DP。
dp[i][j][k][l][m][n] :=（高さnで一番上の4つのブロックの色がi,j,k,lで隣接が同色というペアがm個の時の組み合わせ数）とすると

dp[a0][a1][a2][a3][(b0,b1,b2,b3の上にa0,a1,a2,a3を積み上げた時に隣接ブロックが同色になるペア数) + k][h] += dp[b0][b1][b2][b3][k][h - 1];

と更新できる。
以下ソース。

ll dp[5][5][5][5][8][48];

class TheBrickTowerHardDivTwo {
public:
  int find(int C, int K, int H) {
    ll result = 0;
    memset(dp, 0, sizeof(dp));

    //初期化
    for(int i = 0; i < C; i++)
    for(int j = 0; j < C; j++)
    for(int k = 0; k < C; k++)
    for(int l = 0; l < C; l++){
      //一段目はその段のみで同色ペアがあるか調べる
      int couple = (i == j) + (j == k) + (k == l) + (l == i);
      if(couple <= K)
	dp[i][j][k][l][couple][1] = 1;
    }

    for(int h = 2; h <= H; h++)
    for(int k = 0; k <= K; k++)
    for(int a0 = 0; a0 < C; a0++)
    for(int a1 = 0; a1 < C; a1++)
    for(int a2 = 0; a2 < C; a2++)      
    for(int a3 = 0; a3 < C; a3++)
    for(int b0 = 0; b0 < C; b0++)
    for(int b1 = 0; b1 < C; b1++)
    for(int b2 = 0; b2 < C; b2++)      
    for(int b3 = 0; b3 < C; b3++){
      //二段目以降はその段と一つ下の段で同色ペアを調べる
      int couple = (a0 == b0) + (a1 == b1) + (a2 == b2) + (a3 == b3) + 
	(a0 == a1) + (a1 == a2) + (a2 == a3) + (a3 == a0);
      if(couple + k <= K){
	dp[a0][a1][a2][a3][couple + k][h] += dp[b0][b1][b2][b3][k][h - 1];
	dp[a0][a1][a2][a3][couple + k][h] %= MOD;
      }
    }

    for(int h = 1; h <= H; h++)
    for(int k = 0; k <= K; k++)
    for(int a0 = 0; a0 < C; a0++)
    for(int a1 = 0; a1 < C; a1++)
    for(int a2 = 0; a2 < C; a2++)      
    for(int a3 = 0; a3 < C; a3++)
      result = (result + dp[a0][a1][a2][a3][k][h]) % MOD;
    return result;
  }
};

DPはどうしても詰めが甘くて正解にたどり着かない。