ABC 365

E - Xor Sigma Problem

https://atcoder.jp/contests/abc365/tasks/abc365_e

$\sum_{i,j} f(i,j)$ 系の問題は $i \leq j$ に関する $f(i,j)$ の値を表に書いてみて規則性を見つけると解けることが多い。

\begin{align} f(i,j) &= A_i \oplus A_{i+1} \oplus \cdots \oplus A_j \nonumber \\ S_i &= \sum_{j=i}^N f(i,j) \nonumber \end{align} と定義する。

表: $f(i,j)$ の値

\begin{align} \sum_{i=1}^{N-1} \sum_{j=i+1}^N f(i,j) &= \sum_{i=1}^{N} \left\{ \left( \sum_{j=i}^{N} f(i,j) \right) - f(i,i) \right\} \nonumber \\ &= \sum_{i=1}^{N} \left\{ \left( \sum_{j=i}^{N} f(i,j) \right) - A_i \right\} \nonumber \\ &= \sum_{i=1}^{N} S_i - A_i \nonumber \end{align}

\begin{align} dp_{i,k} &= \sum_{j=i}^N g(i,j,k) \nonumber \\ &\text{ where } g(i,j,k) = \begin{cases} 1 & \text{if } f(i,j) \text{ の } k \text{ bit 目が立っている} \\ 0 & \text{otherwise} \end{cases} \nonumber \end{align}

とすると

\begin{align} S_i = \sum_{k=0} dp_{i,k} \times 2^k \nonumber \end{align}

とかける。($dp_{i,k}$ は $f(i,j), (i \leq j)$ の $k$ bit 目が立っている個数)

また dp の遷移は

\begin{align} dp_{i+1,k} &= \begin{cases} N - i - dp_{i,k} & \text{if } A_i \text{ の } k \text{ bit 目が立っている} \\ dp_{i,k} & \text{otherwise} \end{cases} \nonumber \end{align}

となる。

※ $dp_{i+1,k}$ は $f(i+1,j), (i+1 \leq j)$ の $k$ bit 目が立っている個数を表しており、これは $A_i \oplus f(i,j)$ の $k$ bit 目が立っている個数のことである。($x \oplus x = 0$ よりこれは $A_i$ 分の寄与がなくなることと同義)

void solve() {
    int n;
    cin >> n;
    vll a(n);
    rep(i, n) cin >> a[i];

    vll ones(60, 0);
    ll xorsum = 0;
    ll sum = 0;
    for (ll x : a) {
        xorsum ^= x;
        sum += xorsum;
        rep(i, 60) {
            if ((xorsum >> i) & 1) {
                ones[i]++;
            }
        }
    }

    ll ans = 0;
    rep(i, n) {
        sum -= a[i];
        ans += sum;

        sum = 0;
        rep(j, 60) {
            if ((a[i] >> j) & 1) {
                ones[j] = n - i - 1 - (ones[j] - 1);
            }
            sum += (1ll << j) * ones[j];
        }
    }
    cout << ans << endl;
}