SRM 708 Div2 Hard

問題

https://community.topcoder.com/stat?c=problem_statement&pm=14536

考察

うーん。これ思いつく発想ってどうやるんだろ。

「X[i]を決めた時のiより左、右に分けた時の左側、右側それぞれの文字列が左右対称であることを思いつく」　ことかなぁ

@tookunn_1213
dp[i][j]:=S[0...i]とR[0...j]の共通部分文字列の個数
の間違いでした
失礼しました

— ばたこ (@btk15049) 2017年2月9日

@tookunn_1213 文字列S[i-1] = 文字列R[j-1]の時,dp[i][j] += dp[i-1][j-1]するのは,S[i-1] = R[j-1]からS[i-1]のR[j-1]のペアを回文に含める場合とそうでない場合があるからというのもなんとなく分かった

— tookunn (@tookunn_1213) 2017年2月10日

@tookunn_1213 学校にいるので、帰宅後用メモ pic.twitter.com/aLsmMULoUJ

— tookunn (@tookunn_1213) 2017年2月10日

ソースコード

public class PalindromicSubseq2 {
	static final int MOD = (int)1e9 + 7;

	public int solve(String s){
		char[] S = s.toCharArray();
		char[] R = new StringBuilder(s).reverse().toString().toCharArray();
		int N = S.length;
		long[][] dp = new long[N+1][N+1];

		for(int i = 0;i < N+1;i++){
			dp[i][0] = 1;
			dp[0][i] = 1;
		}

		for(int i = 1;i < N + 1;i++){
			for(int j = 1;j < N + 1;j++){
				dp[i][j] = (dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + MOD) % MOD;
				dp[i][j] %= MOD;
				if(S[i-1] == R[j-1]){
					dp[i][j] += dp[i-1][j-1] % MOD;
					dp[i][j] %= MOD;
				}
			}
		}

		long ans = 0;
		for(int i = 1;i < N + 1;i++){
			ans ^= (dp[i-1][N-i] * i % MOD);
		}
		return (int)ans;
	}
}