Hatena::Grouptopcoder

kojingharangの日記 RSSフィード

2017-02-12

SRM 708 Div1 500 PalindromicSubseq

13:01 |  SRM 708 Div1 500 PalindromicSubseq - kojingharangの日記 を含むブックマーク はてなブックマーク -  SRM 708 Div1 500 PalindromicSubseq - kojingharangの日記  SRM 708 Div1 500 PalindromicSubseq - kojingharangの日記 のブックマークコメント

  • 久しぶりの参加。
  • 長さ 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] 自身)
  • なるほど

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