FourLamps [TopCoderOpen 2017 Round2A Div1 Hard] - はまやんはまやんはまやん

N個のランプがあり、on/offのどちらかの状態をとる。
最初はinitの状態になっている。
ここから、K回以下の操作を繰り返す時に最終的にランプが取りうる状態数は何通りか。

1. 連続する4つのランプを選ぶが、少なくとも1つがonか少なくとも1つがoffで無ければならない
2. この4つのランプの中心を分割点として、N個のランプ全体を前半・後半の2つに分ける
3. 前半・後半のどちらかを選ぶ
4. 選んだ方を反転させる

プロの解法を見るとDPで解いている。
プロからのヒント

TCO2017R2A
250：偶数なら6とc-6、奇数なら3とc-3に分けてチェック
500：距離１の差が１以下の頂点同士に辺を張ってチェック
1000：区間をフリップは考察せずに累積パリティ
— NATSUGIRRRRRI (@natsugir) 2017年5月20日