以下の内容はhttps://kaage.hatenablog.com/entry/2020/07/14/132901より取得しました。

解法

前からDPしていく.

2以上の要素が2連続するとそこから先はすべて埋まり、そうでない場合1を置くか、2以上の要素を置いた後十分になるまで1で埋めるしかない。これを考えると、 $dp\left[i\right]$ を、「 $i$ 要素目以降がまだ決定していない場合の数」としてDPができる。

遷移を Segment Tree で高速化すれば、 $O(N\log N)$ が達成できる。

感想

数え上げDP、バグりがちなので鍛えたい

以上の内容はhttps://kaage.hatenablog.com/entry/2020/07/14/132901より取得しました。
このページはhttp://font.textar.tv/のウェブフォントを使用してます

不具合報告/要望等はこちらへお願いします。
モバイルやる夫Viewer Ver0.14