No.464

まずは $i$ 文字目から $j$ 文字目までが回文になっているかどうかをすべて計算する.

これは, 回文の中心を決め, そこから左右に広げていく方法で $O(N^2)$ で計算できる.

次に $P_1P_2$ と $AP_3$ の切れ目を決める. そしてそのときの $P_1P_2$ の組み合わせの数 ($P_1$ と $P_2$ の切れ目で全探索) と $AP_3$ の組み合わせの数 ($A$ と $P_3$ の切れ目で全探索) を求める. その積がこのときの組み合わせの数である.

$P_1P_2$ と $AP_3$ の切れ目で全探索してそれぞれの組み合わせの数を求め, 総和したものが答えとなる.