SRM 708 DIV1 Medium: PalindromicSubseq
X[i]の値を具体的に求めていこう。
各文字S[i]についてそれぞれX[i]を求める。S[i]がある回文に含まれる場合、S[i]と一致するようなもじS[j]がある。ただし、i=jでS[i=j]が奇数長回文の中心である場合も含む。iとjを総当りで固定した場合、それだけでO(N^2)もかかる。しかし、i,jを固定した場合、事前に計算をしていれば各(i,j)についてO(1)でS[i],S[j]を含むような回文を数えられる。
f[l][r]:=S[l,r)を使った空の文字列も含む回分の個数
g[l][r]
:= Sから得られる回分のうち、偶数長でかつ対になる文字がそれぞれg[0,l)とg(r,n]から得られるものの個数
とする。
l=min(i,j), r=max(i,j)+1とすれば半開区間が得られ、
[l,r)の内側だけでペアになっている回文と、両端だけでペアになっている回文を作れればよく、これは
f[l+1][r-1]*g[l][r]
で求まる。
和をとればX[i]が求まり、Y[i]も求まる。
g[l][r]の求め方は
SRM 708 DIV2 Hard: PalindromicSubseq2 - parukiのブログ
と同様。
f[l][r]はもっと簡単で
f[l][r] = f[l+1][r]+f[l][r-1]-f[l+1][r-1] + (s[l]==s[r-1]ならばf[l+1][r-1]、そうでなければ0)