PalindromicSubseq [SRM 708 : Div1 Med]

問題

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

N文字の文字列Sがある。
X[i] := Sの部分文字列のうちS[i]を含み、回文となる組合せ
Y[i] = i * X[i] % (10^9 + 7)
Y[1] xor Y[2] xor ... xor Y[N]を答えよ。

1 <= N <= 3000

実装

kmjpさんのブログの以下の解説記事を実装した流れを記録した。
kmjp.hatenablog.jp

以下の流れで配列Xを計算する。

struct PalindromicSubseq {
	string S;
	int N;
	int solve(string s) {
		S = s;
		N = s.length();

		calc_dpin();
		calc_dpout();
		calc_f();
		calc_x();

		int ans = 0;
		rep(i, 0, N) {
			int y = 1LL * (i + 1) * x[i] % mod;
			ans ^= y;
		}

		return ans;
	}
};

1. dpin, sminを計算する

int dpin[3010][3010];
int smin[3010][3010];
void calc_dpin() {
	rep(i, 0, 3010) rep(j, 0, 3010) dpin[i][j] = smin[i][j] = 0;
	rep(d, 1, N + 1) rep(l, 0, N - d + 1) {
		int r = l + d - 1;
		if (d == 1)
			dpin[l][r] = smin[l][r] = 1;
		else if (d == 2) {
			if(S[l] == S[r]) dpin[l][r] = 1;
			smin[l][r] = 2 + dpin[l][r];
		} else {
			if (S[l] == S[r]) dpin[l][r] = add(smin[l + 1][r - 1], 1);
			smin[l][r] = add(smin[l + 1][r], smin[l][r - 1], mod - smin[l + 1][r - 1], dpin[l][r]);
		}
	}
}

2. dpout, smoutを計算する

int dpout[3010][3010];
int smout[3010][3010];
void calc_dpout() {
	rep(i, 0, 3010) rep(j, 0, 3010) dpout[i][j] = smout[i][j] = 0;
	rrep(d, N, 1) rep(l, 0, N - d + 1) {
		int r = l + d - 1;

		if (0 < l && r < N - 1) {
			if (S[l] == S[r]) dpout[l][r] = smout[l - 1][r + 1];
			smout[l][r] = add(smout[l][r + 1], smout[l - 1][r], mod - smout[l - 1][r + 1], dpout[l][r]);
		} else {
			if (S[l] == S[r]) dpout[l][r] = 1;
			smout[l][r] = dpout[l][r];
			if (0 < l) smout[l][r] = add(smout[l][r], smout[l - 1][r]);
			else if (r < N - 1) smout[l][r] = add(smout[l][r], smout[l][r + 1]);
			else smout[l][r] = add(smout[l][r], 1);
		}
	}
}

3. fを計算する

int f[3010][3010];
void calc_f() {
	rep(l, 0, N) rep(r, l, N) {
		if (0 < l && r < N - 1) {
			f[l][r] = 1LL * dpin[l][r] * smout[l - 1][r + 1] % mod;
		} else
			f[l][r] = dpin[l][r];
	}
}

4. xを計算する

int x[3010];
void calc_x() {
	rep(i, 0, 3010) x[i] = 0;
	rep(i, 0, N) x[i] = f[i][i];
	rep(l, 0, N) rep(r, l + 1, N) {
		x[l] = add(x[l], f[l][r]);
		x[r] = add(x[r], f[l][r]);
	}
}