diverta 2019 Programming Contest E問題 : XOR Partitioning

問題. XOR Partitioning

数列 が与えられる． の空でない連続部分列への分割で，その連続部分列のビットごとの排他的論理和がすべて等しくなるようなものが何通りあるかを求めよ．

制約： ，　

解法．動的計画法

を含む連続部分列を1つ固定すると，残りの分割で（ビットごとの）排他的論理和がとるべき値が一意に定まる．また，答えに寄与する分割内のすべての連続部分列の排他的論理和はすべて等しく，その値を として排他的論理和による累積和をとると前から となり と 0 が繰り返されることが分かる．そこで， の排他的論理和による累積和を とする． である．

上の考察から， の要素を選択することと，ある連続部分列の右端として選択することを同一視すると， から要素をいくつか選択して が条件を満たす分割であることは，この列が または となっていることである．先頭の要素の選び方は， の要素の種類数なので 通りあり，先頭の要素を決めたときの条件を満たす分割の仕方が何通りあるのかは動的計画法で求める．

動的計画法では， のような列に対して，1番目と最後の要素は必ず選び， と 0 が交互に現れる部分列の個数を求めている．ただし，最後が 0 でない場合は必ず最後の要素が でないとすべての要素を含む分割とならないので注意が必要である．
と の間にある 0 の個数は前もって計算することで各クエリに対して 時間で求まる．また，考慮すべきこのような列の長さの総和は 0 を除くと高々 しかないので，各列に対する動的計画法をその列の長さの線形時間で計算できれば全体も高速に計算可能である．

計算時間：

ソースコードを表示

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const ll MOD = 1e9 + 7;

vector<int> makeNextLink(const vector<int> &a) {
    vector<int> nxt(a.size(), -1);
    map<int, int> memo;
    for (size_t i = nxt.size() - 1; 1 <= i; --i) {
        if (memo.count(a[i]) != 0) nxt[i] = memo[a[i]];
        memo[a[i]] = i;
    }
    return nxt;
}

ll pow2(ll n) {
    ll p = 1;
    for (int i = 0; i < n; ++i) (p *= 2) %= MOD;
    return p;
}

ll Solve() {
    ll n;
    cin >> n;

    vector<int> a(n + 1), cnt_zero(n + 1);
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        a[i] ^= a[i - 1];
        if (a[i] == 0) ++cnt_zero[i];
        cnt_zero[i] += cnt_zero[i - 1];
    }

    // a[i] == a[nxt[i]]
    vector<int> nxt = makeNextLink(a);

    ll num_partition = 1;
    if (a.back() != 0) {
        int idx = 1;
        while (a[idx] != a.back()) ++idx;

        ll sum_a = 1, sum_b = 0;
        while (nxt[idx] != -1) {
            ll num_zero = cnt_zero[nxt[idx]] - cnt_zero[idx - 1];
            (sum_b += num_zero * sum_a) %= MOD;
            (sum_a += sum_b + 1) %= MOD;
            idx = nxt[idx];
        }
        num_partition += sum_b;
    }
    else {
        set<int> used;
        for (int i = 1; i + 1 <= n; ++i) {
            if (used.count(a[i]) != 0) continue;
            used.insert(a[i]);

            if (a[i] == 0) {
                int num_zero = cnt_zero[n] - cnt_zero[i - 1];
                (num_partition += pow2(num_zero - 1) - 1 + MOD) %= MOD;
            }
            else {
                ll sum_a = 1, sum_b = 0, idx = i;
                while (nxt[idx] != -1) {
                    ll num_zero = cnt_zero[nxt[idx]] - cnt_zero[idx - 1];
                    (sum_b += num_zero * sum_a) %= MOD;
                    (sum_a += sum_b + 1) %= MOD;
                    idx = nxt[idx];
                }
                (num_partition += sum_a) %= MOD;
            }
        }
    }

    return num_partition;
}

int main() {
    cin.tie(0); ios::sync_with_stdio(false);

    cout << Solve() << endl;

    return 0;
}

通すので燃え尽きて説明が雑になったけどソースコードを見てもらえば．
計算時間が なのですが，累積和が等しい次の要素を求めるところや， を固定したときの列を重複して求めない処理で map や set を使用せずに直接アドレス表を使用すれば 時間で求まります．ただ， でも通るので・・・．