Cosmos 算法仓库 CodeChef NBONACCI 题解:XOR N-bonacci 序列前缀异或的周期性与 O(n+q) 查询
Cosmos 算法仓库 CodeChef NBONACCI 题解:XOR N-bonacci 序列前缀异或的周期性与 O(n+q) 查询
导读
本文以 Cosmos 开源算法仓库中的 NBONACCI 题目文档 为主体,系统讲解 CodeChef 经典题目 NBONACCI:给定 XOR N-bonacci 序列 F 的前 N 个元素,回答 Q 次关于其前缀异或序列 S 的查询。文中将完整还原题目定义、推导出 S 的周期性这一核心观察,并逐行解析仓库中的 C++ 实现,帮助读者掌握"把看似复杂的无限序列问题化简为 O(n+q) 预处理 + O(1) 查询"的位运算思维。
一、题目背景:什么是 XOR N-bonacci 序列
原文档给出的定义如下:
- N-bonacci 序列:一个无限序列 F₁, F₂, …,满足对每个整数 i > N,Fᵢ 由某个函数 f 作用于前 N 项计算得到,即 Fᵢ = f(Fᵢ₋₁, Fᵢ₋₂, …, Fᵢ₋ₙ)。
- XOR N-bonacci 序列:当 f(Fᵢ₋₁, Fᵢ₋₂, …, Fᵢ₋ₙ) = Fᵢ₋₁ ⊕ Fᵢ₋₂ ⊕ … ⊕ Fᵢ₋ₙ 时(⊕ 表示按位异或),称该序列为 XOR N-bonacci 序列。
- 前缀异或序列 S:Chef 从 F 构造序列 S₁, S₂, …,对每个正整数 i 有 Sᵢ = F₁ ⊕ F₂ ⊕ … ⊕ Fᵢ。给定 F 的前 N 个元素,即可唯一确定整个序列 S。
- 查询要求:回答 Q 个查询,每个查询给定下标 k,输出 Sₖ;题目保证每个 Sₖ 不超过 10⁵⁰。
也就是说,这与常见的"每一项等于前 N 项之和"的斐波那契式递推类似,只是把加法替换成了按位异或,并且要求查询的不是递推序列本身,而是它的前缀异或序列。
该题目收录于仓库的 CodeChef 挑战合集 中,属于典型的需要"观察数学性质再设计算法"的在线评测题目。
二、核心观察:前缀异或序列 S 具有周期 N+1
2.1 递推关系的等价改写
设前缀异或序列定义为:
Sᵢ = F₁ ⊕ F₂ ⊕ … ⊕ Fᵢ
对 XOR N-bonacci 的递推关系做如下变形。当 i > N 时:
Fᵢ = Fᵢ₋₁ ⊕ Fᵢ₋₂ ⊕ … ⊕ Fᵢ₋ₙ
另一方面,考虑两个相邻前缀异或之差:
Sᵢ₋₁ ⊕ Sᵢ₋ₙ₋₁ = (F₁ ⊕ … ⊕ Fᵢ₋₁) ⊕ (F₁ ⊕ … ⊕ Fᵢ₋ₙ₋₁)
利用异或的自反性(x ⊕ x = 0),前后重叠的 F₁ … Fᵢ₋ₙ₋₁ 全部抵消,只剩:
Sᵢ₋₁ ⊕ Sᵢ₋ₙ₋₁ = Fᵢ₋ₙ ⊕ Fᵢ₋ₙ₊₁ ⊕ … ⊕ Fᵢ₋₁ = Fᵢ
而由定义 Sᵢ = Sᵢ₋₁ ⊕ Fᵢ,代入上式得:
Sᵢ = Sᵢ₋₁ ⊕ (Sᵢ₋₁ ⊕ Sᵢ₋ₙ₋₁) = Sᵢ₋ₙ₋₁
2.2 周期性结论
因此对一切 i > N,成立:
Sᵢ = Sᵢ₋ₙ₋₁
这说明前缀异或序列 S 的下标从 i 到 i − (N+1) 呈现完全相等的周期关系,即 S 的周期为 N + 1。
于是任意查询下标 k 都可以归约到前 N + 1 个位置上:
- 若 k mod (N+1) = 0,则 Sₖ = S₀。定义空序列的前缀异或为 0(异或单位元),输出 0;
- 否则 Sₖ = Sₖ mod (N+1),即前 k mod (N+1) 个给定元素的前缀异或。
这正是整个题目的题眼:无需真的构造无限序列,只需 O(n) 预处理前 N 个前缀异或值,即可 O(1) 回答任意查询。
三、仓库实现逐行解析
仓库中的解决方案位于 NBONACCI.cpp,完整代码如下:
#include <iostream>
#include <algorithm>
int main ()
{
int n,q;
std::cin >> n >> q;
int a[n];
for (int i = 0; i < n; ++i)
{
std::cin>>a[i];
}
int x = 0;
int xors[n] = {0};
for (int i = 0; i < n; ++i)
{
x = x ^ a[i];
xors[i] = x;
}
while (q--)
{
int k;
std::cin >> k;
int idx = k % (n + 1);
if (idx > 0)
std::cout << xors[idx - 1] << "\n";
else std::cout << "0\n";
}
return 0;
}
3.1 输入与存储
int n,q;
std::cin >> n >> q;
int a[n];
for (int i = 0; i < n; ++i)
{
std::cin>>a[i];
}
第一行读入 N(XOR N-bonacci 的阶数)与 Q(查询次数);随后读入给定序列 F 的前 N 个元素存入数组 a。
3.2 前缀异或预处理
int x = 0;
int xors[n] = {0};
for (int i = 0; i < n; ++i)
{
x = x ^ a[i];
xors[i] = x;
}
这里用滚动变量 x 累加异或,xors[i] 保存 Sᵢ₊₁ = F₁ ⊕ … ⊕ Fᵢ₊₁(下标 i 从 0 开始,对应序列第 i+1 个前缀异或值)。预处理结束后,xors 数组恰好覆盖了周期段 S₁ … Sₙ。
3.3 查询回答
while (q--)
{
int k;
std::cin >> k;
int idx = k % (n + 1);
if (idx > 0)
std::cout << xors[idx - 1] << "\n";
else std::cout << "0\n";
}
对每个查询 k:
- 计算
idx = k % (n + 1),把 k 归约到周期段内; - 若
idx == 0,说明 k 是 N+1 的整数倍,Sₖ 回落到 S₀ = 0,直接输出0; - 否则输出
xors[idx - 1],即 S_idx。
实现与 2.2 节的数学推导完全一一对应,代码逻辑简洁且没有循环内二次计算,每次查询仅做一次取模与一次数组访问。
四、复杂度与边界情况分析
4.1 时间复杂度
- 预处理阶段:遍历 N 个元素各做一次异或,O(N);
- 查询阶段:每个查询 O(1),总计 O(Q)。
整体复杂度为 O(N + Q),即使 N、Q 都很大也能轻松通过。相比"按递推逐项构造到 max(k) 再回答"的朴素做法 O(max k)(而 k 可能极大),该解法是本质性的优化。
4.2 空间复杂度
只需要一个长度为 N 的 xors 数组,O(N)。
4.3 边界情况注意事项
- k 为 N+1 的倍数:
k % (n+1) == 0时必须输出 0,这是周期性边界,最容易出错,代码中已单独处理; - k 恰好等于 1 … N:
idx就是 k 本身,输出xors[k-1],与直接求前缀异或一致; - 数值范围:原文档保证每个 Sₖ 不超过 10⁵⁰。仓库实现中数组使用
int,在题目数据元素较小(如 32 位整数范围内)时没有问题;若实际数据可能达到 10⁵⁰ 量级,则需要将存储类型替换为 64 位整数或大整数类型,这一约束提醒读者在移植到其他题目时应结合数据范围选择类型; - N = 1 的退化情形:周期为 2,S₁ = F₁,之后 Sᵢ 在 0 与 F₁ 之间交替,代码同样正确覆盖。
五、从本题目看位运算基础:仓库中的异或素材
NBONACCI 的核心是"异或的抵消性"(x ⊕ x = 0),这也是位运算中最高频的武器之一。Cosmos 仓库在 bit_manipulation 目录下集中收录了大量相关实现,可作为复习与延伸材料:
- xor_swap.cpp:利用三次异或实现两数交换(a = a⊕b; b = a⊕b; a = a⊕b),不借助临时变量,体现异或自反性;
- twice_unique_number.cpp:在"其余元素均出现两次、仅两个元素出现一次"的数组中找出这两个唯一元素,先整体异或再按最低置位分组,是本题目周期推导所用"重叠部分抵消"思想的直接应用;
- sum_equals_xor.cpp:统计满足 x + n = x ⊕ n 的 x 的数量,体现加法与异或之间"无进位相加"的关系;
- lonely_integer、hamming_distance 等目录还提供了更多异或与位运算的经典练习题。
理解这些基础实现后,再回看 NBONACCI 的周期推导,会发现它们共用同一套思维模型:用异或的性质消去重复、寻找周期、化简状态。
六、编译运行与验证
该解法是标准 C++ 程序,无第三方依赖,可按以下方式在本仓库环境中编译运行:
g++ -std=c++11 -O2 -o nbonacci NBONACCI.cpp
输入格式为:
N Q
F1 F2 ... FN
k1
k2
...
kQ
例如输入(N=2, Q=3,给定 F₁=1, F₂=2,查询 k=1, 3, 6):
2 3
1 2
1
3
6
验证:F₃ = F₂ ⊕ F₁ = 3;S₁ = 1,S₂ = 3,S₃ = 0(周期 N+1=3),S₆ = S₀ = 0。程序输出依次为 1、0、0,与推导一致。
总结
NBONACCI 是一道典型的"先证明数学性质、再设计高效算法"的竞赛题。通过将 XOR N-bonacci 的递推改写为前缀异或序列的等式 Sᵢ = Sᵢ₋ₙ₋₁,问题从"无限序列任意位置查询"坍缩为"长度为 N+1 的周期表查询",最终在 O(N + Q) 时间内解决。本文结合 Cosmos 仓库的 题目文档 与 参考实现,完整覆盖了定义、推导、实现、复杂度与边界情况,读者可将这一"找周期 + 前缀异或"的套路迁移到其他异或递推类问题中。