いろはちゃんコンテスト Day2 E - 連呼
AAA
が登場しない列を数えて(NN+M−2)から引く方針が良さそう。
とりあえず、最初の文字と最後の文字の制限がないとして考えてみる。AAA
が登場しない列とは、A
とAA
をM個のB
の間に挿入してできる列である。A
をd個にわけるとして、A
がx個、AA
がy個になったとすると、
x+2y=N
x+y=d
より、y=N−d,x=2d−Nと整理できる。A
とAA
の並べ方は(yd)通りあり、M個のB
への挿入の仕方は(両端を含めると)(dM+1)通りある。したがって、総和は∑d(dM+1)(yd)となる。(有効なdについてだけ計算する。)
さて、最初の文字がA
で最後の文字がB
という制限を満たすものを数える。最初がAB
から始まるパターンとAA
から始まるパターンにわけて数えることにする。
最初がAB
から始まる場合、最後がB
なので、AB·B·...·B
の·
で示したM−1箇所から選んでA
かAA
を挿入することになる。総和は∑d(dM−1)(yd)である。ただし、x+2y=N−1,x+y=d だからy=N−1−dである。
最初がAA
から始まる場合、AAB·B·...·B
の·
で示したM−1箇所から選んでA
かAA
を挿入することになる。総和はやはり∑d(dM−1)(yd)である。ただし、x+2y=N−2,x+y=d だからy=N−2−dである。