思路

考慮轉化成組合數學
一個數最終會被異或多少次, 等價于在給出的網格圖中, 有多少種路徑走到這個位置
顯然是一個 \(\displaystyle {a \choose b}\) 的組合數形式

又有

不難發現若確定 \(a\), 我們直接枚舉 \(a\) 子集就可以 \(\mathcal{O} (2^{\text{popcount}(a)})\) 做一次

考慮優化
若用第 \(t\) 行來計算, 對于 \((t, i)\) 對 \((x, y)\) 的貢獻是 \(\displaystyle {x - t \choose i - y}\)
若我們讓 \(t = x \bmod 512\), 則只用 \(\mathcal{O} (nB)\) 預處理, 后面的 \(\mathcal{O} (2^{\text{popcount}(x - t)})\) 為原來的根號級別
總復雜度是一個根號分治級別的 \(\mathcal{O} (n \sqrt{n} + q \sqrt{n})\)

#include <bits/stdc++.h>
#define int long long

const int MAXN = 3e5 + 10;

int a[MAXN];
int n, q;
int b[520][MAXN];

signed main() {
    scanf("%lld", &n);
    for (int i = 0; i < n; i++) {
        scanf("%lld", &a[i]);
        b[0][i] = a[i];
    }
    for (int i = 1; i < 512; i++) for (int j = 0; i + j < n; j++) b[i][j] = b[i - 1][j] ^ b[i - 1][j + 1];
    scanf("%lld", &q);
    while (q--) {
        int x, y;
        scanf("%lld%lld", &x, &y);
        if (x < 512) {
            printf("%lld\n", b[x][y]);
        } else {
            int t = x % 512;
            int ans = b[t][y];
            for (int yy = x - t; yy; yy = (yy - 1) & (x - t)) {
                if (t + y + yy < n)
                    ans ^= b[t][y + yy];
            }
            printf("%lld\n", ans);
        }
    }
    return 0;
}

總結

觀察力過于敏銳了
找到令 \(t = x \bmod 2^p\) 的性質之后, 我們可以用少的 \(p\) 來降低大量的 \(\mathcal{O} (2^{\text{popcount}(x - t)})\), 而且前面的 \(\mathcal{O} (n2^p)\) 預處理也可以接受