\(A[l:r]\) で \((A_l,A_{l+1},\dots,A_r)\) を表します．

準備：偶数長の擬回文の数え上げ

\(\mathrm{suf}(i)\) を， \(A[1:i]\) の suffix であって偶数長の擬回文であるもの（空であるものも含む）の個数とします．同様に， \(\mathrm{pref}(i)\) を， \(A[i:2N]\) の prefix であって偶数長の擬回文であるものの個数とします．

各数字に乱数を割り当てて累積 XOR を見ることで， \(\mathrm{suf}(i)\) と \(\mathrm{pref}(i)\) を各 \(i=1,2,\dots,2N\) に対して期待 \(O(N)\) 時間で高い確率で求めることができます．

奇数長の擬回文の数え上げ

いくつか用語と記号を定義します．

• 奇数長の擬回文で，値が unique な要素の index をその擬回文の 中心 と呼ぶ．
• 良い擬回文 を，奇数長の擬回文であって，その任意の prefix および suffix が偶数長の擬回文でないものと定義する．
• \(A\) において，値 \(v\) が1回目に現れる index を \(L(v)\), 2回目に現れる index を \(R(v)\) とする．
• 値 \(v\) が index \(i\) を またぐ とは， \(L(v) < i < R(v)\) であることとする．

奇数長の擬回文は，「偶数長の擬回文 + 良い擬回文 + 偶数長の擬回文」と一意的に分解できます． \(\mathcal{S}_i\) を，次を満たす正整数 \((l,r)\) の組の全体とします．

• \(l \leq i \leq r\)
• \(A[l:r]\) は， \(i\) を中心とする良い擬回文である

すると， \(i\) を中心とする擬回文の個数は， \(\displaystyle \sum_{(l,r)\in \mathcal{S}_i} \mathrm{suf}(l-1) \times \mathrm{pref}(r+1)\) と求まります． 実は， \(\mathcal{S}_i\) の要素数の総和はたかだか \(4N\) であり，高速に列挙することができます．

\(A\) の長さ \(1\) の部分列はすべて良い擬回文です．長さ \(3\) 以上の良い擬回文の列挙を考えます．

\(A[l:r]\) が \(i\) を中心とする良い擬回文であるとします．このとき， \(A_i\) は \(l\) または \(r\) のどちらか一方をまたぎます． \(r\) をまたぐ場合を考えます． \(A_i\) は， \(r\) をまたぐ値 \(v\) のうち， \(L(v)\) が最大のものです． もしある \(v'\) が存在して， \(v'\) が \(r\) をまたぎ，かつ \(i < L(v')\) が成り立つならば，\(A[l:r]\) は \(v'\) を一つだけ含むことになり， \(i\) が中心であることに矛盾するからです．

よって， \(r\) を固定したとき，中心の候補 \(i\) は一意に定まります．実際に \(i\) が中心となりうるかの判定および \(l\) の取得は，偶数長の擬回文を数え上げたときと同様にハッシュを用いておこなえます．

\(l\) をまたぐ場合も同様です．

以上より，全体で期待 \(O(N)\) 時間で問題を解くことができました．

実装例 (C++)