diverta 2019 E - Xor Partitioning
diverta 2019 Programming Contest E - XOR Partitioning
自分の頭が弱くなりすぎていて悲しい,どうにかしていきたい
4完した時点で11位だったのにね,そっからなにもできなかったね
unratedになっていただき助かった
問題概要
N
要素の数列 A
が与えられる.
これをいくつかの区間に分けるような 通りのうち,それぞれの区間のxorが等しくなるようなものはいくつあるか.
解法
数列全体のxorが0でなければその値
X
がそれぞれの区間の値になることがわかる.- この場合は求めるのが簡単.僕は詰めきれなかったけど.
prefixから偶数個の区間のxorを取ると0になる
- prefixのxorが0になるような点で区切れば2つの区間ずつ考えていける
最初に累積xor, B
を取っておいて考える.
ここで と置く.
また, も持つ.
を更新するタイミングは B
に0が登場したタイミングだが,ここで毎回行うと になってしまうので,次に B
の中で が登場したときに更新するように遅延評価することにする.
の更新の式は3.を利用すると, となることがわかる.
当然これをそのまま行うと遅延評価しようと計算量大爆発になってしまう.
と式変形すると,右辺は しかiに依存しないので, , とする.
となり, それぞれ , と更新することができる.
また, が現れる前に0が複数回現れているときのことを考える.
0が現れただけこの更新を行うと再び計算量大爆発なので,で終わらせたい気持ちになる.cntが変化しないことを考慮すると,
となるので, は一回やったときと同じ結果になる. の変化は,更新した回数(同じ値) が足し込まれるので,それまでに処理した0の個数と今の位置までの0の個数を持っとけばその差だけかけた値を足し込めばできる.
実際に解を出力する際には,総xorが0の場合と0以外の場合で分ける.
0のとき
まず遅延評価のうち評価できてない分を評価する.
それぞれの区間のxorが0になるような分け方は,0が B
に現れる回数を としたとき, になるので別で計算する.
xorが になるような分け方は, なので, これを答えに足す.
0以外のとき
A
の総xorを とすると, が解になるが,これは既に計算していて なのでこれを出力する.
int main(void){ cin.tie(0); ios::sync_with_stdio(false); int64 N; cin >> N; vector<int64> A(N); REP(i, N) cin >> A[i]; vector<Mint> dp(1 << 20, 0), dp2(1 << 20, 1), dp3(1 << 20, 0); vector<int64> cnt(1 << 20, 0), zok(1 << 20, 0); int64 xx = 0; int64 zero = 0; REP(i, N) { xx ^= A[i]; if (xx == 0) { zero++; } else { if (zok[xx] != zero) { dp[xx] = dp2[xx] * cnt[xx] - dp3[xx]; dp2[xx] += dp[xx] * Mint(zero - zok[xx]); dp3[xx] += (dp[xx] * cnt[xx]) * Mint(zero - zok[xx]); zok[xx]++; } zok[xx] = zero; } cnt[xx]++; } Mint res = 0; if (xx == 0) { FOR(i, 1, dp.size()) { if (zok[i] != zero) dp[i] = (dp2[i] * cnt[i] - dp3[i]); res += dp[i]; } res += Mint(2).pow(zero-1); cout << res << endl; } else { if (zok[xx] != zero) { dp[xx] = dp2[xx] * cnt[xx] - dp3[xx]; dp2[xx] += dp[xx] * Mint(zero - zok[xx]); dp3[xx] += (dp[xx] * cnt[xx]) * Mint(zero - zok[xx]); } cout << dp2[xx] << endl; } }