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)

 

f:id:parukii:20170304141911j:plain