形式化题目

给定一个长度为 $N$ 的数组 $a_0, a_1, \dots, a_{N-1}$，有一个无限大的二维数组 $f$，定义如下：

• $f_{0, i} = a_i$ $(0 \le i \le N-1)$
• 对于 $j \ge 1$，且 $i+j \le N-1$，有 $f_{j, i} = f_{j-1, i} \oplus f_{j-1, i+1}$

给定 $Q$ 次查询，每次查询给出一对 $(x, y)$，输出 $f_{x, y}$ 的值。

保证查询满足 $0 \le x, y$ 且 $x+y \le N-1$。

数据范围：

• $N, Q \le 100,000$

正解

思路

根据题目的递推式 $f_{j, i} = f_{j-1, i} \oplus f_{j-1, i+1}$，可以发现它的结构类似于杨辉三角（二项式系数）。如果我们把它展开，可以得到 $f_{x, y}$ 的一般表达式：

即，$f_{x, y}$ 是 $a_{y+k}$ 的异或和，其中 $k$ 必须满足 $\binom{x}{k}$ 是奇数。

由 Lucas 定理，$\binom{x}{k} \bmod 2 \equiv 1$ 等价于二进制下 $k$ 是 $x$ 的子集（即 (k & x) == k）。 所以：

现在问题变成了求所有满足 $k$ 是 $x$ 的子集的 $a_{y+k}$ 的异或和。 每次查询如果直接枚举 $x$ 的子集，最坏情况下 $x$ 的二进制中有 16 个 1，枚举次数为 $2^{16} = 65536$，这在 $Q=10^5$ 的情况下会超时。

高低位分块优化：

我们把 $x$ 拆成高位和低位两部分。取块大小 $B = 8$ 位，即 $2^8 = 256$。 把 $x$ 拆成 $x_1 = \lfloor x / 256 \rfloor$ 和 $x_2 = x \bmod 256$。 那么 $x = (x_1 \ll 8) + x_2$。$k$ 也可以拆成 $k_1$ 和 $k_2$，其中 $k_1 \subseteq x_1$ 且 $k_2 \subseteq x_2$。

因此有：

我们可以在 $O(N \cdot 2^8)$ 的时间内预处理出所有 $f_{j, i}$，其中 $0 \le j < 256$。 预处理的转移方程可以通过 $O(1)$ 的 lowbit 操作实现：$f_{j, i} = f_{j \setminus \text{lowbit}(j), i} \oplus f_{j \setminus \text{lowbit}(j), i+\text{lowbit}(j)}$。

对于每次查询，由于 $x_2 < 256$，我们只需要枚举 $x_1$ 的所有子集 $k_1$。$x_1$ 的最大值为 $10^5 \gg 8 \approx 390$，二进制下最多有 8 位为 1，枚举子集的时间复杂度不超过 $2^8 = 256$。

总时间复杂度为预处理 $O(N \cdot 2^8)$ 和查询 $O(Q \cdot 2^8)$，可以通过此题。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-09 21:00
# update_at: 2026-10-09 21:16

import sys
from functools import reduce
from operator import xor

BITS = 8                                    # 低位块宽，低位状态数 2**8 = 256
SIZE = 1 << BITS
HIGH = 1 << (BITS + 1)                      # x < 2**17 ⇒ x>>8 ≤ 390 < 512，高位子集表留一倍余量

# SUBS[i] = i 的全部子集左移 BITS 位后组成的列表，查询时按 i = x>>BITS 直接查表
SUBS = [[k << BITS for k in range(i + 1) if k & i == k] for i in range(HIGH)]


def build_low_table(a: list[int], n: int) -> list[list[int]]:
    """返回 f：f[j][i] = XOR_{k ⊆ j} a[i + k]，即低位部分恰为 j 的询问答案。

    取 j 的最低位 low，按"不取 low / 取 low"拆成两支递推：
    f[j][i] = f[j ^ low][i] ^ f[j ^ low][i + low]。
    第 j 行只会被下标 < n - j 的询问读到，其余位置补 0 占位。
    """
    f = [a] + [None] * (SIZE - 1)
    for j in range(1, SIZE):
        low = j & -j
        prev = f[j ^ low]
        keep = n - j
        row = list(map(xor, prev[:keep], prev[low:keep + low])) if keep > 0 else []
        f[j] = row + [0] * ((n - keep) if keep > 0 else n)
    return f


def solve() -> None:
    data = sys.stdin.buffer.read().split()
    if len(data) < 2:
        return                              # 空输入/只有半行：直接退出，不做越界假设
    n, q = int(data[0]), int(data[1])
    if n <= 0 or len(data) < 2 + n:
        return                              # n=0 或序列长度不足：输入非法，不强行算
    a = [int(v) for v in data[2:2 + n]]

    f = build_low_table(a, n)

    out = []
    pos = 2 + n
    if len(data) < pos + 2 * q:
        return                              # 查询行数不足：输入非法，不强行算
    for _ in range(q):
        x, y = int(data[pos]), int(data[pos + 1])
        pos += 2
        low_row = f[x & (SIZE - 1)]         # 低位查预处理表，高位枚举子集异或
        out.append(str(reduce(xor, (low_row[y + off] for off in SUBS[x >> BITS]), 0)))

    sys.stdout.write('\n'.join(out) + ('\n' if out else ''))


if __name__ == '__main__':
    solve()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-09 21:00
 * update_at: 2026-10-09 21:14
 */
// 20030《异或查询》：Lucas 定理 + 高低位分块
// b[x][y] = XOR_{k ⊆ x} a[y + k]（组合数 C(x,k) 的奇偶性由 Lucas 定理给出 k & x == k）。
// 低 BLOCK_BITS 位的答案全部预处理，查询时只枚举高位的子集。
#include <iostream>

using namespace std;
typedef long long ll;

const int MAXN = 100005;
const int BLOCK_BITS = 8;                    // 低位块宽，低位状态数 2^8 = 256
const int BLOCK_SIZE = 1 << BLOCK_BITS;

int a[MAXN];                    // 题面输入的初始序列
int f[BLOCK_SIZE][MAXN];        // f[j][i] = XOR_{k ⊆ j} a[i + k]，即低 BLOCK_BITS 位为 j 的答案

// 预处理低位表。j 去掉最低位 p 后得到 p_prev，则子集枚举可拆成
// "不取 p" 与 "取 p" 两支，故 f[j][i] = f[p_prev][i] ^ f[p_prev][i + p]。
void build_low_table(int n) {
    for (int i = 0; i < n; i++) {
        f[0][i] = a[i];
    }
    for (int j = 1; j < BLOCK_SIZE; j++) {
        int p = j & -j;            // j 的最低位，作为本次拆分的位权
        int p_prev = j ^ p;
        for (int i = 0; i + j < n; i++) {
            f[j][i] = f[p_prev][i] ^ f[p_prev][i + p];
        }
    }
}

// 单次询问：x 拆成低位 x2 与高位 x1，枚举 x1 的全部子集 k1，
// 每项查表 f[x2][y + (k1 << BLOCK_BITS)] 后异或起来。
int query(int x, int y) {
    int x2 = x & (BLOCK_SIZE - 1);
    int x1 = x >> BLOCK_BITS;

    int ans = 0;
    int k1 = x1;
    while (true) {
        ans ^= f[x2][y + (k1 << BLOCK_BITS)];
        if (k1 == 0) break;        // 子集枚举必须先用完 k1 = 0 再退出，否则漏项
        k1 = (k1 - 1) & x1;        // 枚举 x1 子集的标准位技巧
    }
    return ans;
}

void solve() {
    int n, q;
    if (!(cin >> n >> q)) return;

    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    build_low_table(n);

    for (int i = 0; i < q; i++) {
        int x, y;
        cin >> x >> y;
        cout << query(x, y) << "\n";
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
    return 0;
}

复杂度

• 时间复杂度： 预处理部分对于每一个 $0 \le j < 2^8$，计算了 $N$ 个状态，时间复杂度为 $O(N \cdot 2^8)$。 每次查询枚举高位子集，最多枚举 $2^8$ 个子集，时间复杂度为 $O(Q \cdot 2^8)$。 总时间复杂度为 $O((N+Q)2^8)$。
• 空间复杂度： 预处理数组 f 需要大小为 $2^8 \times N$，空间复杂度为 $O(N \cdot 2^8)$，约 25MB，符合要求。

总结

1. 算法核心：通过 Lucas 定理将组合数模 2 的问题转化为子集枚举，再通过高低位分块思想，平衡预处理与查询的时间，将查询复杂度从 $O(Q \cdot 2^{\text{popcount}(x)})$ 优化为 $O((N+Q)2^{8})$。
2. 证据层升级与对拍结论：本题不再是无数据题。官方提供的大数据样例 xor.in/xor.ans（规模 $N=Q=100,000$）在验证中与 main.cpp 和 main.py 的输出逐字节一致。worker 跨源对拍结论表明代码在大规模数据下表现优异且正确。
3. 数据规模与块大小：$N=Q=100,000$，这恰好适合块大小取 $B=8$（即 256）。预处理复杂度为 $N \times 256$，查询复杂度不超过 $256$，常数很小，足以在限定时间内通过。
4. 溢出处理（T9 五项）：本题递推只涉及异或操作，没有加减乘除。由于异或操作本质上是不进位加法，其中间结果始终不会超过操作数原有的最大位宽（$a_i$ 为普通整数范围内），所以使用 32 位整型 int 即可，不会发生溢出。