SRM555 Div2 Hard

955

DP1[ n ] = n マス連続して泥でないときの行き方が偶数通りか奇数通りか。
DP2[どこまで見た][泥のマスがいくつか][ 偶数通りの行き方がこれまであったか ]

o を乾いたマス、x を泥のマスとした場合、oooxoooo の行き方は"3マス連続して泥でない道の行き方"×"4マス連続して泥でない道の行き方"になる。
つまり、泥のマスで区切ったそれぞれの連続して泥でない道の行き方の中に偶数通りの行き方のある部分があれば、
全体も偶数通りの行き方が存在することになる(偶x偶=偶、偶x奇=偶、奇x奇=奇)。


前計算で n マス連続して泥でない場合の行き方を計算しておく。
その後、ある2つの泥のマスの間にいくつの乾いたマスを挿入するかというDPを行う。
両端に泥のマスを付け加えるとやりやすかった。

view plainprint?

1. class MuddyRoad2 {  
2. public:  
3.   int theCount(int N, int muddyCount)  
4.   {  
5.     const lli mod = 555555555;  
6.   
7.     const int M = 560;  
8.     lli dp1[M];  
9.     fill(dp1, dp1 + M, 0);  
10.     dp1[0] = 0;  
11.     dp1[1] = 1;  
12.     dp1[2] = 1;  
13.     for (int i = 3; i < M; ++i) {  
14.       dp1[i] += dp1[i - 1] + dp1[i - 2];  
15.       dp1[i] %= 2;  
16.     }  
17.   
18.     lli dp2[M][M][2];  
19.     fill(&dp2[0][0][0], &dp2[M - 1][M - 1][2 - 1] + 1, 0);  
20.     dp2[0][0][false] = 1;  
21.   
22.     for (int i = 0; i < M; ++i) {  
23.       for (int m = 0; m <= muddyCount; ++m) {  
24.         for (int flg = 0; flg <= 1; ++flg) {  
25.           if (dp2[i][m][flg] == 0) continue;  
26.           for (int j = 0; i + j + 1 < M; ++j) {  
27.             if (i == 0 && j == 0) continue;  
28.             if (j == 0 && i + j + 1 == N + 1) continue;  
29.             int next = flg || (dp1[j] % 2 == 0);  
30.             dp2[i + j + 1][m + 1][next] += dp2[i][m][flg];  
31.             dp2[i + j + 1][m + 1][next] %= mod;  
32.           }  
33.         }  
34.       }  
35.     }  
36.   
37.     return dp2[N + 1][muddyCount + 1][true];  
38.   }  
39. };  

class MuddyRoad2 {
public:
  int theCount(int N, int muddyCount)
  {
    const lli mod = 555555555;

    const int M = 560;
    lli dp1[M];
    fill(dp1, dp1 + M, 0);
    dp1[0] = 0;
    dp1[1] = 1;
    dp1[2] = 1;
    for (int i = 3; i < M; ++i) {
      dp1[i] += dp1[i - 1] + dp1[i - 2];
      dp1[i] %= 2;
    }

    lli dp2[M][M][2];
    fill(&dp2[0][0][0], &dp2[M - 1][M - 1][2 - 1] + 1, 0);
    dp2[0][0][false] = 1;

    for (int i = 0; i < M; ++i) {
      for (int m = 0; m <= muddyCount; ++m) {
        for (int flg = 0; flg <= 1; ++flg) {
          if (dp2[i][m][flg] == 0) continue;
          for (int j = 0; i + j + 1 < M; ++j) {
            if (i == 0 && j == 0) continue;
            if (j == 0 && i + j + 1 == N + 1) continue;
            int next = flg || (dp1[j] % 2 == 0);
            dp2[i + j + 1][m + 1][next] += dp2[i][m][flg];
            dp2[i + j + 1][m + 1][next] %= mod;
          }
        }
      }
    }

    return dp2[N + 1][muddyCount + 1][true];
  }
};