迷いませんか?

継続しないを座右の銘に

diverta 2019 E - Xor Partitioning

diverta 2019 Programming Contest E - XOR Partitioning

自分の頭が弱くなりすぎていて悲しい,どうにかしていきたい
4完した時点で11位だったのにね,そっからなにもできなかったね
unratedになっていただき助かった

問題概要

N 要素の数列 A が与えられる.
これをいくつかの区間に分けるような  2^{N-1} 通りのうち,それぞれの区間のxorが等しくなるようなものはいくつあるか.

解法

  1. 数列全体のxorが0でなければその値 X がそれぞれの区間の値になることがわかる.

    • この場合は求めるのが簡単.僕は詰めきれなかったけど.
  2. prefixから偶数個の区間のxorを取ると0になる

    • prefixのxorが0になるような点で区切れば2つの区間ずつ考えていける
  3. 累積xorが0になるような区間の中に x が現れる場合,そこで区切るとそれぞれの区間のxorは x になる

最初に累積xor, B を取っておいて考える.

ここで  dp \lbrack i \rbrack \lbrack x \rbrack := \lbrack 0, i \rbrackをxorがxになる区間に分ける方法 と置く.
また,  cnt \lbrack i \rbrack \lbrack x \rbrack := B の \lbrack 0, i ) にxが今まで何回登場したか も持つ.
 dp \lbrack x \rbrack を更新するタイミングは B に0が登場したタイミングだが,ここで毎回行うと  O(NA_{max}) になってしまうので,次に B の中で  x が登場したときに更新するように遅延評価することにする.

 dp \lbrack i \rbrack \lbrack x \rbrack の更新の式は3.を利用すると,  dp \lbrack i \rbrack \lbrack x \rbrack = \sum dp_{j} \lbrack j \rbrack \lbrack x \rbrack \times (cnt \lbrack i \rbrack \lbrack x \rbrack - cnt \lbrack j \rbrack \lbrack x \rbrack) となることがわかる.
当然これをそのまま行うと遅延評価しようと計算量大爆発になってしまう.
 dp \lbrack i \rbrack = cnt \lbrack i \rbrack \sum dp \lbrack j \rbrack - \sum dp \lbrack j \rbrack \times cnt \lbrack j \rbrack と式変形すると,右辺は  cnt \lbrack i \rbrack しかiに依存しないので,  dp2 := \sum dp \lbrack j \rbrack ,  dp3 := \sum dp \lbrack j \rbrack \times cnt \lbrack j \rbrack とする.
 dp = cnt \times dp2 - dp3 となり, それぞれ  dp2 = dp2 + dp dp3 = dp3 + dp \times cnt と更新することができる.

また,  x が現れる前に0が複数回現れているときのことを考える.
0が現れただけこの更新を行うと再び計算量大爆発なので, O(1)で終わらせたい気持ちになる.cntが変化しないことを考慮すると,

 \displaystyle \begin{aligned}
dp2' &= dp2 + dp \\ 
dp3' &= dp3 + dp \times cnt \\
dp' &= cnt \times dp2' - dp3' \\
    &= cnt \times (dp2 + dp) - (dp3 + dp \times cnt) \\
    &= cnt \times dp2 - dp3
\end{aligned}

となるので, dp は一回やったときと同じ結果になる. dp2, dp3 の変化は,更新した回数(同じ値)  dp が足し込まれるので,それまでに処理した0の個数と今の位置までの0の個数を持っとけばその差だけかけた値を足し込めばできる.

実際に解を出力する際には,総xorが0の場合と0以外の場合で分ける.

0のとき

まず遅延評価のうち評価できてない分を評価する.
それぞれの区間のxorが0になるような分け方は,0が B に現れる回数を  K としたとき, 2^{K-1} になるので別で計算する.
xorが  x になるような分け方は,  dp \lbrack N \rbrack \lbrack x \rbrack なので, これを答えに足す.

0以外のとき

A の総xorを  x とすると,  \sum dp \lbrack i \rbrack \lbrack x \rbrack が解になるが,これは既に計算していて  dp2 なのでこれを出力する.

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