重要：この記事は青コーダー以上を想定読者としています。B問題の解説を求めている方は他の解説を参照してください。

\(N:=|S|\) とします。公式解説 で存在のみが言及されている \(O(N(\log N)^2)\) 解法を解説します。

この記事では、列の添字のindexは0から始まるものとします。

前座

定理：
長さ \(N\) の数列 \(A,B\) が与えられたとき、\(C_k=\sum_{i+j=k,\ i<j}A_iB_j\) により定まる数列 \(C\) は \(O(N(\log N)^2)\) で求めることができる。

証明：
数列に対する二項演算 \(*\) を \((A*B)_k=\sum_{i+j=k}A_iB_j\) と定める。
数列に対する二項演算 \(*'\) を \((A*'B)_k=\sum_{i+j=k,\ i<j}A_iB_j\) と定める。
数列に対する二項演算 \(+\) を \((A+B)_k=A_k+B_k\) と定める。
長さ \(N\) の数列 \(A\) に対し、後半を \(0\) クリアした数列を \(A^L=(A_0,A_1,\ldots,A_{\lfloor N/2\rfloor -1},0,0,\ldots,0)\)、前半を 0 クリアした数列を \(A^R:=(0,0,\ldots,0,A_{\lfloor N/2\rfloor },A_{\lfloor N/2\rfloor +1},\ldots,A_{N-1})\) と定める。
このとき、\(A*'B=A^L*'B^L+A^L*B^R+A^R*'B^R\) となる。第 \(2\) 項は FFT により求まり、第 \(1\) 項と第 \(3\) 項は(0である部分を適切に取り除いて)再帰的に計算することで、長さ \(N\) の数列 \(A,B\) に対して \(A*'B\) は \(O(N(\log N)^2)\) で求められることがわかる。

本題

\(A_i=\begin{cases} 1 && \text{if } S_i=\text{A}\\ 0 && \text{if } S_i\neq\text{A} \end{cases}\)
\(C_i=\begin{cases} 1 && \text{if } S_i=\text{C}\\ 0 && \text{if } S_i\neq\text{C} \end{cases}\)
と数列 \(A,C\) を定める。\(j\) を固定したとき、問題の条件を満たす \(i,k\) の組の個数は \(\sum_{x>0}A_{j-x}C_{j+x}\) となるが、\(\sum_{x>0}A_{j-x}C_{j+x}=\sum_{i+k=2j,\ i<k}A_iC_k=(A*'C)_{2j}\) なので、\(A*'C\) を求めることで全ての \(j\) について求めることができる。よって \(O(N(\log N)^2)\) でこの問題を解くことができた。