AtCoder Beginner Contest 167 E - Colorful Blocks

解法

「隣り合うブロックの組であって同じ色で塗られている組」がちょうど $k$ 個あるとして、 $k=0, 1, ..., K$ についてそれぞれ求めた場合の数を合計することで答えを求めます。

ブロックは全部で $N$ 個なので、ブロックが隣り合っている箇所は $N-1$ 箇所です。このうちブロックが同じ色である箇所を $k$ 個選ぶ選び方は $_{N-1}C_{k}$ 通りです。

そして選んだ箇所を挟んだブロック同士は同じ色にしなければいけないので、結合してしまうと考えましょう。

f:id:betrue12:20200511092714p:plain

図で示すように、ブロックが同じ色である $k$ 箇所の選び方がどのようなものであっても、結合後のブロックは $N-k$ 個になります。そしてこれらのブロックの間は先ほど選ばなかった箇所なので、隣り合うブロック同士は異なる色である必要があります。

つまり「 $N-k$ 個のブロックに、隣り合うブロックの色が異なるように色を塗る方法の数」を求めれば良いです。これは、

と考えると、 $M(M-1)^{N-k-1}$ 通りと計算することができます。

よって、 $_{N-1}C_{k} \times M(M-1)^{N-k-1}$ を $k=0, 1, ..., K$ について合計すれば答えを求めることができます。