整数対 \((i,k)\) に対して \(A_i = A_{i+1} = \dots = A_{i+k-1} = k\) となってはいけないという条件に対して包除原理を適用します。

ここで、以下の補題が成り立ちます。

閉区間 \([1,N]\) を \([1,M],[2,M+1],\dots,[N-M+1,N]\) で完全に網羅する方法のうち、\((-1)^{使った区間の個数}\) の総和は以下のようになる。

\( \left\{ \begin{array}{ll} 1 & N \bmod (M+1) = 0 \\ -1 & N \bmod (M+1) = -1 \\ 0 & \mathrm{else} \end{array} \right. \)

証明は漸化式を解けば従います。この補題を使うと、以下のような \(\mathrm{O}(N^2)\) 解法を導くことが出来ます。

・\(dp[i] = A_1,A_2,\dots,A_i\) に対して上記の包除原理を適用したときの \((-1)^k\) の総和

更新は、以下の \(3\) 通りのパターンに分かれます。

・\(A_{i+1}\) を含む包除原理の区間を使わない場合の \(dp[i]\) から \(dp[i+1]\) への遷移

・\(A_{i+1},\dots,A_j\) が全て \(-1\) であるため、この区間を \((k,x)\) のタイプの区間で覆うような遷移(あらかじめ \((k,?)\) ごとに上記の補題の総和を \(\mathrm{O}(N\log N)\) で前計算しておく)

・\(A_{i+1},\dots,A_j\) に正の要素が \(1\) 種類のみ存在するため、この区間を \((A_k,x)\) のタイプの区間で覆うような遷移

そして、この遷移は \(2\) 番目の遷移を \(-1\) が連続する部分ごとにまとめて分割統治で処理し、\(3\) 番目の遷移が \(1\) 種類の正の要素の値 \(A_k\) で平方分割で処理することで \(\mathrm{O}(N\sqrt N)\) に高速化することが出来ます。

実装例(C++,10ms)

https://atcoder.jp/contests/arc169/submissions/48440752

更に高速化することもできます。\(2\) 番目の遷移を分割統治でなく fps inv にすることで \(\mathrm{O}(N\log N)\) に、\(3\) 番目の遷移が \(dp[i]\) に入ってくるこのタイプの種類の \(A_k\) の種類数が \(\mathrm{O}(1)\) であることを利用すると累積和で \(\mathrm{O}(N)\) で処理できます。よって、この問題を \(\mathrm{O}(N\log N)\) で解くこともできます。(この部分は noshi91 さんに教えていただきました。ありがとうございます。)