i番目まで見た時に、i+1番目を違う色で塗るパターンは$ M-1通り $ a[i] を左からi番目までを隣接する色を異なるようにした場合の塗り方とすると$ a[i] =M(M-1)^i 隣同士を同じ色で塗る場合、それらを1つと見做すと異なる色で塗る場合で考えられる $ K個同じ色で隣接して良い場合、$ N-K個のブロックと考えられる ただし、…