SRM 708 DIV2 Hard: PalindromicSubseq2

dp[i][j]:=左は文字iまで、右側はjまで見たときの偶数長(長さ0以上)の回分の個数の数(ただし1<=i<=j<=N)

たとえば、文字列sが以下のような形の場合(1-indexed)

abcxycba

abc...ba

dp[3][7] = 2^2 = 4

1<=j-i<=nを

nから順に確定していけばいい。つまり

dp[i][j]

= dp[i-1][j] + dp[i][j+1] - dp[i-1][j+1] + (s[i]==s[j]?dp[i-1][j+1]:0)

= dp[i-1][j] + dp[i][j+1] - (s[i]==s[j]?0:dp[i-1][j+1])