<-- home

AtCoder ABC098 D

April 27, 2020

https://atcoder.jp/contests/abc098/tasks/arc098_b

D - XOR Sum 2

が成り立つかどうかを2bitとかで調べればわかるが、2進数で考えてどこかの桁でくり上がりが発生すると、になる。また、が成り立つなら、その部分列についても繰りあがりは発生していないわけだから、条件を満たすの組の個数はしゃくとり法で数え上げられる。

今回の問題では、必ず使う必要があるわけではないが、であること(とXORは可換、結合的であること)を用いると、が累積和の考えを用いて計算できる(実装1)。

実装2は、解説にあるように、各桁の1の個数について累積和で計算しておいて、について、すべての桁の1の個数が1個以下なら繰り上がりなし、そうでないなら繰り上がりが発生することを使って数えている。

実装1

#define MAX_BIT 20

int main() {
    i64 N; cin >> N;
    vector<i64> A(N);
    REP(i, N) cin >> A[i];

    vector<i64> P(N + 1, 0);
    vector<i64> X(N + 1, 0);
    REP(i, N) P[i + 1] = P[i] + A[i];
    REP(i, N) X[i + 1] = X[i] ^ A[i];

    i64 cnt = 0;
    i64 right = 0;
    REP(left, N) {
        auto cond = [&]() {
            return (P[right + 1] - P[left]) == (X[right + 1] ^ X[left]);
        };
        while (right < N && cond()) {
            right++;
        }
        cnt += right - left;
    }
    cout << cnt << endl;

    return 0;
}

実装2

#define MAX_BIT 20

vector<i64> N1[MAX_BIT + 1];

int main() {
    i64 N; cin >> N;
    vector<i64> A(N);
    REP(i, N) cin >> A[i];

    i64 p = 1 << MAX_BIT;
    RREP(b, MAX_BIT + 1) {
        N1[b].resize(N + 1);
        N1[b][0] = 0;
        REP(i, N) {
            N1[b][i + 1] = N1[b][i] + A[i] / p;
            A[i] %= p;
        }
        p /= 2;
    }

    i64 cnt = 0;
    i64 right = 0;
    REP(left, N) {
        auto cond = [&]() {
            bool ok = true;
            REP(i, MAX_BIT + 1) {
                if (N1[i][right + 1] - N1[i][left] > 1) ok = false;
            }
            return ok;
        };
        while (right < N && cond()) {
            right++;
        }
        cnt += right - left;
    }
    cout << cnt << endl;

    return 0;
}