包除原理を考えます。

問題文の条件は、以下の2つの条件を満たすことと同値です。

• （条件A）色が塗られた区間の長さは偶数であり、区間を長さ2ずつのブロックに分割すると各ブロックを構成する2つのマスは同じ色で塗られている
• （条件B）上記の通りブロックに分けたとき、隣接するブロック同士の色は異なる

条件Bがない場合は比較的簡単な動的計画法によって答えを求めることができるので、条件Bに違反するものを包除原理を使って除くことを考えます。具体的には、\(i\)番目までの色の塗り方を決めたとき、条件Aを満たすような塗り方であって条件Bに明示的に違反する箇所を \(2\) で割ったあまりが\(j \in \{0, 1\}\)であるような場合の数を \(dp_{i, j}\)とすると、解は \(dp_{n, 0} - dp_{n, 1}\)であり、DPの状態数は \(O(N)\) です。

遷移に関しては、貰うDPを考えるとマス \(i\) を塗ることができる各マスについて \(\bmod 4\) で同じものは明示的に条件Bに違反させた回数の偶奇を変えないことに注意すると、\(i \bmod 4\) と \(j\) の値ごとに遷移可能な各色についてのDPの値の総和を \(8\) 通り保持しておけば \(O(1)\) で計算可能であることがわかります。