2017-02-12

SRM 708 Div1 500 PalindromicSubseq

13:01 |

久しぶりの参加。

長さ 1≦N≦3000 の文字列 s が与えられる。
X[i] = "s[i] を含む s の部分列のうちそれが回文になるものの個数 mod 10^9+7" とする
i in [0, N) に対して (i+1)*X[i] の XOR を求めよ。

ひょ〜
サンプルを見て初めて問題の意味が分かる
SRM 中に出たアイデアや考察
- 回文ということは中央に軸があるので軸の位置を全部試す感じでいけないか？
- 軸の左右にどちらもある文字しか使われない
- L, R より外で回文のとき、内側は何通り?
さっぱり
おわり

あとで
上位陣のをいくつか見る

s[i] を必ず採用する時、部分列が回文になるなら s[i] の反対側に対応する同じ文字があるはずである。(s[i] が中央なら s[i] 自身)
なるほど

SRM708 500の上位陣のコードを見て何でこれで解けるんだろうとしばらく考えてたら分かった気がする。

特に後半がナゾだったが回文中で固定文字に対応する文字は重複なくN通りあるから足せば良いのかと気付いたところなう。
— 暇人の名は (@kojingharang) 2017年2月11日

s[i] が決まればそれに対応する文字の位置は N 種類
s[i], 対応する文字を左から L, R とすると ? ? ? L * * * R ? ? ? という形で表せる
内側(*)だけで回文になる部分列の個数と外側(?)だけで回文になる部分列の個数を N^2 DP で求めておけば
L, R が決まったときの組み合わせ総数は内側回文個数 * 外側回文個数 O(1) で求まる
X[i] を計算するときは L, R の組み合わせは N 通りなので X[i] は O(N) で求まる
全体 O(N^2)
内側 : dp1[i][j] ... [i, j] 内の部分列かつ回文の個数
外側 : dp2[i][j] ... [0, i), (j, N) 内の部分列かつ回文の個数
として書いてみたが内外共に半開区間の方がいろいろすっきりするのかもしれない。

DP2つとそれを組み合わせる処理を正確に書かないといけないので難しい.....

Accepted in practice

class PalindromicSubseq {
	public:
	int solve(string s) {
		ll N = s.size();
		// dp1[i][j] ... [i, j] 内での回文の個数
		vector<vector<modll>> dp1(N, vector<modll>(N));
		// dp2[i][j] ... [0, i), (j, N) 内での回文の個数
		vector<vector<modll>> dp2(N, vector<modll>(N));
		RANGE(L, 0, N+1) REP(i, N-L+1) {
			int j = i+L-1;
			if(L==0) {
				if(0<=j && i<N) dp1[i][j] = 1; // empty
			} else {
				modll v = 0;
				// s[i] を採用しない場合 (s[j]は採用するしないどちらも含む)
				if(i+1<N) v += dp1[i+1][j];
				// s[j] を採用しない場合 (s[i]は採用するしないどちらも含む)
				if(0<=j-1) v += dp1[i][j-1];
				// s[i], s[j] 両方採用しない場合が 2 回数えられている分を減らす
				if(0<=j-1 && i+1<N) v -= dp1[i+1][j-1];
				if(s[i]==s[j]) {
					// s[i], s[j] を採用できる。採用するとその内側の組み合わせ総数だけ増える
					if(0<=j-1 && i+1<N) v += dp1[i+1][j-1];
				}
				dp1[i][j] = v;
			}
		}
		for(int L=N;L>=1;L--) REP(i, N-L+1) {
			int j = i+L-1;
			if(L==N) {
				dp2[i][j] = 1; // empty
			} else {
				modll v = 0;
				// 同様
				if(0<=i-1) v += dp2[i-1][j];
				if(j+1<N) v += dp2[i][j+1];
				if(0<=i-1 && j+1<N) {
					v -= dp2[i-1][j+1];
					if(s[i-1]==s[j+1]) {
						// s[i-1], s[j+1] を採用できる。採用するとその外側の組み合わせ総数だけ増える
						v += dp2[i-1][j+1];
					}
				}
				dp2[i][j] = v;
			}
		}
		ll ans = 0;
		REP(i, N) {
			modll X = 0;
			REP(j, N) {
				if(s[i]==s[j]) {
					ll I=i, J=j;
					if(I>J) swap(I, J);
					// ここでは I, J がどちらも採用され I, J が回文にて対応関係にある。
					// 内側は [I+1, J-1] 内の回文の個数
					// 外側は [0, I), (J, N) 内の回文の個数
					// これらの積が "I, J がどちらも採用され回文にて I, J が対応関係にある" 場合の組み合わせ総数。
					X += (I+1<=J-1 ? dp1[I+1][J-1] : modll(1)) * dp2[I][J];
				}
			}
			ans ^= modll(i+1LL)*X;
		}
		return ans;
	}
};

kojingharangの日記

2017-02-12

SRM 708 Div1 500 PalindromicSubseq