読者です 読者をやめる 読者になる 読者になる

tookunn’s diary

主に競技プログラミング関係

SRM 708 Div2 Hard

考察

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

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

ソースコード

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;
	}
}