これ、てんぷら君のおかげで随分とシンプルな問題になった！

問題へのリンク

問題概要

$N$ 個の 0 以上の整数 $A_{1}, \dots, A_{N}$ が与えられる。各 $k = 1, 2, \dots, N$ に対して、

$X = A_{1}$ xor $A_{2}$ xor $\dots$ xor $A_{k}$ としたときの
$(A_{1}$ xor $X) + (A_{2}$ xor $X) + \dots + (A_{k}$ xor $X)$ の値を求めよ。

制約

$1 \le N \le 3 \times 10^{5}$
$0 \le A_{i} \lt 2^{30}$

解法

XOR に関する問題は各桁ごとに考えるのは常套手段ではある。つまり、各桁 $d$ に対して、次のように考える。

$A_{1}, \dots, A_{k}$ の中に $d$ 桁目が 1 になっているものの個数を $P$ としたとき、次のようになる。
- $P$ が奇数ならば $X$ の $d$ 桁目は 1
- $P$ が偶数ならば $X$ の $d$ 桁目は 0
これを踏まえて、 $(A_{1}$ xor $X), (A_{2}$ xor $X), \dots, (A_{k}$ xor $X)$ のうち、 $d$ 桁目が 1 となっているものの個数 $Q$ は次のように求められる。
- $P$ が奇数のときは $A_{1}, \dots, A_{k}$ の $d$ 桁目が 0-1 反転するので、 $Q = k - P$
- $P$ が偶数のときは、 $Q = P$

このようにして求めた $Q$ に対して、 $Q \times 2^{d}$ を合計していけば答えが求められる。

差分更新へ

上記の作業を $k = 1, 2, \dots, N$ に対して順に実施していく必要がある。しかし、 $P, Q$ の値は、差分だけ見て更新することが可能である。

よって、全体の計算量は、 $D$ を最大の桁数として $O(ND)$ で抑えられる。

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int N; cin >> N;
    vector<long long> a(N);
    for (int i = 0; i < N; ++i) cin >> a[i];

    const int DIGIT = 35;
    vector<int> ones(DIGIT, 0);
    for (int k = 0; k < N; ++k) {
        long long res = 0;
        for (int d = 0; d < DIGIT; ++d) {
            if (a[k] & (1LL<<d)) ++ones[d];
            res += (1LL<<d) * (ones[d] % 2 == 0 ? ones[d] : k+1 - ones[d]);
        }
        printf("%lld\n", res);
    }
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

CPSCO2019 Session3 E - Enumerate Xor Sum (500 点設定)

問題概要

制約

解法

差分更新へ