TopCoder SRM 708 Div2 Hard PalindromicSubseq2

ネタ切れなのかなぁ。
https://community.topcoder.com/stat?c=problem_statement&pm=14536

問題

Div1 Mediumの亜種。
TopCoder SRM 708 Div1 Medium PalindromicSubseq - kmjp's blog

Div1 MediumはX[i]はS[i]を含む回文の数だったが、こちらではX[i]はS[i]を回文の中心とするような回文の数を表す。

解法

Div1 Mediumがわかっていれば簡単。
X[i] = OutSum(i-1,i+1)なので、Div1の解法が一部流用できる。

ll mo=1000000007;
ll douts[3030][3030];

class PalindromicSubseq2 {
	public:
	int solve(string S) {
		int N=S.size();
		int i,d,j;
		
		ZERO(douts);
		
		FOR(i,N+2) douts[0][i]=douts[i][N+1]=1;
		for(d=N;d>=1;d--) {
			for(i=1;i+d-1<=N;i++) {
				int j=i+d-1;
				ll ret=douts[i-1][j] + douts[i][j+1] - douts[i-1][j+1] + mo;
				if(S[i-1]==S[j-1]) ret += douts[i-1][j+1];
				douts[i][j]=(ret+mo)%mo;
			}
		}
		
		ll ret=0;
		FOR(i,N) ret ^= 1LL*(i+1)*douts[i][i+2]%mo;
		return ret;
	}
}

まとめ

最近またDiv2 HardがDiv1 Mediumと似通ってるな。