Submission #5368692

---

Source Code Expand

#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; (i) < (int)(n); ++ (i))
#define REP3(i, m, n) for (int i = (m); (i) < (int)(n); ++ (i))
#define REP_R(i, n) for (int i = (int)(n) - 1; (i) >= 0; -- (i))
#define REP3R(i, m, n) for (int i = (int)(n) - 1; (i) >= (int)(m); -- (i))
#define ALL(x) begin(x), end(x)
using namespace std;

template <int32_t MOD>
struct mint {
    int32_t value;
    mint() = default;
    mint(int32_t value_) : value(value_) {}
    inline mint<MOD> operator + (mint<MOD> other) const { int32_t c = this->value + other.value; return mint<MOD>(c >= MOD ? c - MOD : c); }
    inline mint<MOD> operator * (mint<MOD> other) const { int32_t c = (int64_t)this->value * other.value % MOD; return mint<MOD>(c < 0 ? c + MOD : c); }
    inline mint<MOD> & operator += (mint<MOD> other) { this->value += other.value; if (this->value >= MOD) this->value -= MOD; return *this; }
    inline mint<MOD> & operator *= (mint<MOD> other) { this->value = (int64_t)this->value * other.value % MOD; if (this->value < 0) this->value += MOD; return *this; }
    mint<MOD> pow(uint64_t k) const {
        mint<MOD> x = *this, y = 1;
        for (; k; k >>= 1) {
            if (k & 1) y *= x;
            x *= x;
        }
        return y;
    }
};
template <int32_t MOD> mint<MOD> operator * (int64_t value, mint<MOD> n) { return mint<MOD>(value) * n; }

template <class OperatorMonoid>
struct dual_segment_tree {
    typedef typename OperatorMonoid::underlying_type operator_type;
    typedef typename OperatorMonoid::target_type underlying_type;
    int n;
    vector<operator_type> f;
    vector<underlying_type> a;
    const OperatorMonoid op;
    dual_segment_tree() = default;
    dual_segment_tree(int a_n, underlying_type initial_value, OperatorMonoid const & a_op = OperatorMonoid()) : op(a_op) {
        n = 1; while (n < a_n) n *= 2;
        a.resize(n, initial_value);
        f.resize(n - 1, op.unit());
    }
    underlying_type point_get(int i) { // 0-based
        underlying_type acc = a[i];
        for (i = (i + n) / 2; i > 0; i /= 2) { // 1-based
            acc = op.apply(f[i - 1], acc);
        }
        return acc;
    }
    void range_apply(int l, int r, operator_type z) { // 0-based, [l, r)
        assert (0 <= l and l <= r and r <= n);
        range_apply(0, 0, n, l, r, z);
    }
    void range_apply(int i, int il, int ir, int l, int r, operator_type z) {
        if (l <= il and ir <= r) { // 0-based
            if (i < f.size()) {
                f[i] = op.append(z, f[i]);
            } else {
                a[i - n + 1] = op.apply(z, a[i - n + 1]);
            }
        } else if (ir <= l or r <= il) {
            // nop
        } else {
            range_apply(2 * i + 1, il, (il + ir) / 2, 0, n, f[i]);
            range_apply(2 * i + 2, (il + ir) / 2, ir, 0, n, f[i]);
            f[i] = op.unit();
            range_apply(2 * i + 1, il, (il + ir) / 2, l, r, z);
            range_apply(2 * i + 2, (il + ir) / 2, ir, l, r, z);
        }
    }
};

struct plus_operator_monoid {
    typedef int underlying_type;
    typedef int target_type;
    int unit() const { return 0; }
    int append(int a, int b) const { return a + b; }
    int apply(int a, int b) const { return a + b; }
};

constexpr int MOD = 1e9 + 7;
constexpr int K = 20;
mint<MOD> solve(int n, const vector<int> & a) {
    vector<int> acc(n + 1);
    partial_sum(ALL(a), acc.begin() + 1, bit_xor<int>());

    if (acc[n] != 0) {
        vector<mint<MOD> > dp(n + 1);
        vector<mint<MOD> > foo(1 << K);
        dp[0] = 1;
        foo[0] += dp[0];
        REP3 (r, 1, n + 1) {
            dp[r] += foo[acc[n] ^ acc[r]];
            foo[acc[r]] += dp[r];
        }
        return dp[n];

    } else {
        vector<array<mint<MOD>, 2> > dp(1 << K);
        dual_segment_tree<plus_operator_monoid> zero(1 << K, 0);
        REP3 (b, 1, 1 << K) {
            dp[b][false] = 1;
        }
        zero.range_apply(1, 1 << K, 1);
        REP3 (r, 1, n + 1) {
            if (acc[r] == 0) {
                zero.range_apply(1, 1 << K, 1);
            } else {
                int k = zero.point_get(acc[r]);
                zero.range_apply(acc[r], acc[r] + 1, -k);
                dp[acc[r]][false] += k * dp[acc[r]][true];
                dp[acc[r]][true] += dp[acc[r]][false];
            }
        }
        REP3 (b, 1, 1 << K) {
            int k = zero.point_get(b);
            assert (k != 0);
            dp[b][false] += k * dp[b][true];
        }

        mint<MOD> ans = 0;
        ans += mint<MOD>(2).pow(count(ALL(acc), 0) - 2);  // for 0
        REP3 (b, 1, 1 << K) {
            ans += dp[b][1];
        }
        return ans;
    }
}

int main() {
    int n; cin >> n;
    vector<int> a(n);
    REP (i, n) {
        cin >> a[i];
        assert (a[i] < (1 << K));
    }
    cout << solve(n, a).value << endl;
    return 0;
}

Submission Info

Judge Result