484.1

SRM

550

スタックに4種類のものを詰め込む。上のL個が同じ種類のものだった場合には、L個まとめて取り出すことができるとする。このとき、N個のものを詰め込むときに、最終的に全部取り出せるようなパターンは何通りあるか答えよ、という問題。


取り敢えず、全部取り出せるように詰め込む必要があるので、実際に詰め込む順番じゃなくて、長さNの全部取り出せる列を作ることを考える。長さXの列が全部取り出せるとき、L個のものを追加して全部取り出せるようにするには、X+1通り入れ方がある。実際には右端と左端両方に入れることを考えると、入れた順番が逆の場合をダブルカウントしていることになるので、どちらかの端には入れないようにする。また、L個のものを入れたときに、両隣が同じ種類のものの場合も、一つ左か右に入れた場合と区別できないので、そういうケースも入れないようにする。


まとめると、長さXの全部取り出せる列のある場所にL個のものを入れたいが、左端には入れない。右端には任意の種類が入れられるが、それ以外の場所には右隣と同じ種類のものは入れられない。また、入れていく過程でP番目に入れたならばPよりも左に改めて追加することは重複なのでやらない。つまり、右側にいくつ入れられる場所が残っているか(同じ種類のが入れられないだけなので、種類は気にしなくて良い)というのを覚えておくだけ。


後はDPでこれを計算していくだけ。一つ入れた場合L-1個入れられる場所が増える。これは同じ場所には入れない(同じ場所に入れることは右端に追加することでカウントされている)ため。また、入れ終わった後に、右側に残っている入れられる場所がP個ならば、次に入れられる場所についてそのすべてを考慮しなくてはならず、単純にやるとその計算がN^2になる。なので、右側に入れられる場所がP-1個残るパターンとうまくまとめて計算してやる必要がある。(0番目から順番にやっていくのでもいいと思う。)

int count[] = "右側にP個入れられる場所があるもののパターン数";
int next[] = "更新用";
long sum = 0;
p = "一番入れられる場所が多いものの位置";
for(int i=p; i>0; --i) {
  // 右端のときだけ任意の種類を入れられる;
  sum += count[i] * (i == 1 ? 4L : 3L);
  sum %= mod;
  // 入れられる場所はL-1個増える;
  next[i + L - 1] += sum;
}
for(int i=0; i<L-1; ++i) { next[i] += sum; }
count = next;
// これをN個挿入するまで(N/L回)繰り返す;


もしかしたらテーブルは1個でいいのかも知れない。