\(2\) 文字以上の回文にならないということは, aa のように同じ文字が並んだ部分か aba のように1文字挟んで同じ文字が並んだ部分のどちらも存在しないということである.

\(i\) 文字目まで見たときの \(i\) 文字目が \(j\) で \(i-1\) 文字目が \(k\) となる組み合わせの数を \(D(i, j, k)\) とすると,

\[D(i, j, k) = \sum_{l='a', l \neq j}^{'z'} D(i-1, k, l)\]

となる. ただし, \(D(i, j, j) = 0\) である.

これを DP で計算するのだが, そのままやると間に合わない. そこで上式の \(\sum\) の部分で累積和を使えばなんとか間に合う.