問題atcoder.jp\(N\) 個のマスと \(M\) 種類の色があり、色 \(i\) はマス \(L _ i,L _ i+1,\ldots,R _ i\) にのみ塗っていいとする。さらに、各マスについて「そのマスに色が塗られているならば、隣り合うマスのうちちょうど 1 マスが同じ色で塗られていないといけない」という条件があるとして、ありえる \(N\) マスの塗り方の個数を求める問題である。解法問題の言い換えまず、この問題をラフに言い換えると、以下の条件を全て満たすような \(N\) マスの塗り方の個数を求める問題となる。 同じ色は、必ずちょうど 2 マス連続して塗られていなければならな…
