题解 | #小苯的最短路#

1. 问题分析

题目给出了一个 个点的无向完全图（Complete Graph），任意两点 之间的边权定义为 （按位异或）。 目标是计算起点 到所有点 () 的最短路长度 的异或和，即 。

• 数据组数 。
• 由于 高达 ，这直接否定了任何 、 甚至 的算法。标准的图论算法（如 Dijkstra 或 Floyd）完全不可用。
• 必须寻找 的数学解法（对于每组测试数据）。

问题的关键在于快速确定 的值。一旦 有了通项公式，剩下的就是对异或和的数学推导。

2. 最短路性质证明

2.1 最短路推导

我们需要确定从点 到点 的最短路径。 直觉上，直接走边 的代价是 。 是否存在一条中间路径 使得总代价更小？

路径 的总代价（代数和）为：

我们需要比较这个代数和（）与直接连接的异或值（）之间的关系。 由异或运算的性质可知，对于任意非负整数 ，有： 由于 ，必然有 ，因此：

令 。 则 。 代入不等式得：

结论： 三角形两边之和（代数加法）永远大于等于第三边（边权为异或值）。这意味着增加中间节点永远不会减少路径长度。 因此，从 到 的最短路就是直接连接的边。

2.2 目标转化

我们需要计算的是所有 的异或和 ：

利用异或的结合律和交换律，我们可以将常数 和变量 分离：

这个问题被分解为两个子问题：

1. 常数异或和部分： 个 的异或和。
2. 前缀异或和部分： 到 的异或和。

3. 数学优化

为了在 时间内解决问题，我们需要处理上述两个部分。

3.1 处理常数部分

异或运算满足 。

• 如果 是偶数，有偶数个 相异或，结果为 。
• 如果 是奇数，有奇数个 相异或，结果为 。
• 这等价于 。

3.2 处理前缀异或和

记 。 前缀异或和呈现出以 4 为周期的规律：

• 当 时，
• 当 时，
• 当 时，
• 当 时，

证明简述（通过归纳法）： 观察每4个数一组 的二进制性质，可以发现其异或和恒为 0（忽略最高位影响，低位异或抵消）。具体规律是计算机科学中的经典结论。

3.3 最终逻辑整合

4. 算法复杂度分析

4.1 时间复杂度

• 分析： 对于每一组测试数据，我们只需要进行一次模运算、几次逻辑判断和常数次位运算。不涉及循环或递归。
• 结果： 单组数据 ，总复杂度 。对于 ，计算量极小，完全满足要求。

4.2 空间复杂度

• 分析： 仅需要存储 和几个中间变量，不需要数组或图的数据结构（如邻接矩阵/邻接表）。
• 结果： 。

5. 代码实现

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;

    auto f = [](int n) -> int {
        int r = n % 4;
        if (r == 0) {
            return n;
        } else if (r == 1) {
            return 1;
        } else if (r == 2) {
            return n + 1;
        } else if (r == 3) {
            return 0;
        }
        return 0;
    };

    while (T--) {
        int n;
        cin >> n;
        int ans = n % 2;
        ans ^= f(n);
        cout << ans << "\n";
    }
}