Cosmos 算法仓库 CodeChef NBONACCI 题解:XOR N-bonacci 序列前缀异或的周期性与 O(n+q) 查询

原创2026-09-22 13:48:541,911 阅读
文章标签:教程示例工程

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:

  1. 计算 idx = k % (n + 1),把 k 归约到周期段内;
  2. 若 idx == 0,说明 k 是 N+1 的整数倍,Sₖ 回落到 S₀ = 0,直接输出 0;
  3. 否则输出 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 仓库的 题目文档 与 参考实现,完整覆盖了定义、推导、实现、复杂度与边界情况,读者可将这一"找周期 + 前缀异或"的套路迁移到其他异或递推类问题中。

登录后查看全文
cosmos