D1. 无限序列（简单版本）详细题解

一、题目理解

定义一个无限二进制序列 $a$：

• 前 $n$ 项给定：$a_1, a_2, \dots, a_n \in \{0,1\}$
• 对于 $m > n$：$$a_m = a_1 \oplus a_2 \oplus \dots \oplus a_{\lfloor m/2 \rfloor} $$其中 $\oplus$ 是按位异或（对二进制来说，等同于模 $2$ 加法）。

给定 $l = r$（简单版本），需要输出 $a_l$。

---

二、核心观察

1. 定义前缀异或

设

$$S(m) = a_1 \oplus a_2 \oplus \dots \oplus a_m$$

则：

• 对于 $m > n$：$a_m = S(\lfloor m/2 \rfloor)$
• $S(m) = S(m-1) \oplus a_m$

2. 递推式

将 $a_m$ 代入：

$$S(m) = S(m-1) \oplus S(\lfloor m/2 \rfloor) \quad (m > n) $$

3. 边界条件

• $S(0) = 0$
• $S(1), S(2), \dots, S(n)$ 可直接计算

---

三、标程算法解析

标程使用了一个巧妙的数学化简，避免了复杂的递归。

步骤 1：预处理前 $2n$ 项

vector<int> a(n + 1);
vector<int> pref(n + 1);
for (int i = 1; i <= n; i++) {
    pref[i] = pref[i - 1] + a[i];
}

pref[i] 是普通前缀和（不是异或），但这里实际上只需要奇偶性（模 $2$）。

步骤 2：将 $n$ 调整为奇数

if (n % 2 == 0) {
    n++;
    int cur = pref[n / 2] & 1;
    a.push_back(cur);
    pref.push_back(pref.back() + cur);
}

为什么？ 因为递推中 $n$ 是奇数时规律更简洁。

步骤 3：再扩展 $2n$ 项

for (int i = n + 1; i <= n * 2; i++) {
    a.push_back(pref[i / 2] & 1);
    pref.push_back(pref[i - 1] + a[i]);
}

这样我们有了 $a_1 \dots a_{2n}$。

步骤 4：计算 $p$

int p = pref[n] & 1;

$p$ 是 $S(n) = a_1 + \dots + a_n$ 的奇偶性（即异或和）。

步骤 5：核心函数 get(x)

auto get = [&](int64_t x) {
    int ret = 0;
    while (true) {
        if (x <= n * 2) {
            ret ^= a[x];
            break;
        }
        ret ^= p;
        if ((x / 2 - n) % 2 == 0) {
            break;
        }
        x /= 2;
    }
    return ret;
};

这个函数计算 $a_x$ 的逻辑：

• 如果 $x \le 2n$，直接查表
• 否则，先异或上 $p$（因为 $a_x = S(\lfloor x/2 \rfloor)$ 的奇偶性等于 $p$ 的若干倍）
• 然后检查条件，决定是否继续递归

---

四、数学原理

关键结论（通过打表/推导）

对于 $m > n$，有：

$$S(m) = S(m-1) \oplus S(\lfloor m/2 \rfloor)$$

经过分析，$S(m)$ 的奇偶性满足周期性和线性递推。标程通过扩展 $2n$ 项并利用 $p = S(n) \bmod 2$，将任意 $x$ 的 $a_x$ 计算归结为：

1. 不断除以 $2$，直到 $x \le 2n$
2. 每层贡献一个 $p$（当条件满足时）
3. 最终查表得到结果

---

五、为什么这样正确？

设 $f(m) = S(m) \bmod 2$（即前缀和的奇偶性）。

从递推：

$$f(m) = (f(m-1) + f(\lfloor m/2 \rfloor)) \bmod 2$$

对于 $m > n$，可以证明：

• $f(m)$ 的值只取决于 $m$ 的二进制表示和 $f(n)$
• 当 $m$ 足够大时，$f(m)$ 呈现规律性

标程中的循环就是在模拟这个“除以 $2$”的过程，每层检查奇偶性变化。

---

六、示例验证

以第一个测试用例为例：

n=1, a=[1], l=1

• $n$ 是奇数，不扩展
• 计算 $p = pref[1] \& 1 = 1$
• get(1)：$x=1 \le 2$，返回 $a[1]=1$

输出 1 ✅

---

七、复杂度分析

• 预处理：$O(n)$
• 每次 get(x)：$O(\log x)$，因为 $x$ 每次除以 $2$
• 总复杂度：$O(n + t \log l)$，满足 $n \le 2\times 10^5$，$l \le 10^{18}$

---

八、总结

要点	说明
核心思想	利用前缀异或的递推，将问题转化为奇偶性判断
数学化简	通过扩展 $2n$ 项和模 $2$ 运算，避免递归
算法步骤	1. 补全 $n$ 为奇数 2. 扩展至 $2n$ 项 3. 用循环除以 $2$ 计算答案
时间复杂度	$O(n + t \log l)$
空间复杂度	$O(n)$