ABC167 E - Colorful Blocks (500)
i番目まで見た時に、i+1番目を違う色で塗るパターンは$ M-1通り
$ a[i] を左からi番目までを隣接する色を異なるようにした場合の塗り方とすると$ a[i] =M(M-1)^i
隣同士を同じ色で塗る場合、それらを1つと見做すと異なる色で塗る場合で考えられる
$ K個同じ色で隣接して良い場合、$ N-K個のブロックと考えられる
ただし、隣接する場所は$ _{N-1}C_K個ある
$ K 個隣接して良い場合の数は $ a[N-K] \times _{N-1}C_{K}
全体で$ O(N+K)