AtCoder题解｜ABC 121D XOR World

题目信息 📚

【题目描述】

Let $f(A, B)$ be the exclusive OR (XOR) of $A, A+1, \ldots, B$. Find $f(A, B)$.

【输入】

The input is given from Standard Input in the following format:

$A$ $B$

【输出】

Compute $f(A, B)$ and print it.

【数据范围】

All values in the input are integers.

$0 \leq A \leq B \leq 10^{12}$

【输入样例1】

2 4

【输出样例1】

【输入样例2】

123 456

【输出样例2】

【输入样例3】

123456789012 123456789012

【输出样例3】

123456789012

【题目来源】

https://atcoder.jp/contests/abc121/tasks/abc121_d

题目解析 🍉

【题目分析】

本题需要计算 $f(A, B)$

我们定义 $f(n) = 1 \oplus 2 \oplus \ldots (n-1) \oplus n$ ，则有：

$f(A-1) \oplus f(B) = (1 \oplus 2 \oplus \ldots \oplus A-1) \oplus (1 \oplus 2 \oplus \ldots A-1 \oplus A \oplus A+1 \oplus \ldots B)=(1 \oplus 2 \oplus \ldots \oplus A-1) \oplus (1 \oplus 2 \oplus \ldots A-1) \oplus (A \oplus A+1 \oplus \ldots B)=0 \oplus (A \oplus A+1 \oplus \ldots B) = f(A, B)$

因此我们只需要找方法快速求出 $f(n) = 1 \oplus 2 \oplus \ldots (n-1) \oplus n$ 即可。

关于异或的重要性质：

当 $n$ 为偶数时，有 $n \oplus n+1 = 1$
对于任意自然数 $n$，有 $n \oplus n = 0$

因此我们可以采用以下形式：

当 $n$ 为奇数时，有 $f(n) = 1 \oplus (2 \oplus 3) \ldots (n-1 \oplus n) = 1 \oplus 1 \oplus … \oplus 1 \oplus n$
当 n 为偶数时，有 $f(n) = 1 \oplus (2 \oplus 3) \ldots (n-2 \oplus n-1) \oplus n = 1 \oplus 1 \oplus … \oplus 1 \oplus n$

因此只需要统计能够组成 1 的个数即可。

当 $n$ 为奇数时，$f(n) = 1 \oplus (2 \oplus 3) \ldots (n-1 \oplus n) $
- 若 $cnt_1 = (n+1)/2$ 为偶数：所有组成的1两两配对消去，结果为 $0$
- 若 $cnt_1 = (n+1)/2$ 为奇数：偶数对的1两两配对消去，留下1个$1$，结果为 $1$
当 n 为偶数时，有 $f(n) = 1 \oplus (2 \oplus 3) \ldots (n-2 \oplus n-1) \oplus n $
- 若 $cnt_1 = (n)/2$ 为偶数：所有组成的1两两配对消去，结果为 $0 \oplus n = n$
- 若 $cnt_1 = (n)/2$ 为奇数：偶数对的1两两配对消去，留下1个$1$，结果为 $1 \oplus n$

根据以上结论，我们就可以书写相应代码了。

但是以上结论有点复杂，我们可以通过数学方式简化结论，去除奇偶性（这里不予证明）

对于$f(n) = 1 \oplus 2 \oplus \ldots (n-1) \oplus n$，有：

$n \mod 4 == 0$ 时，$f(n) = n$

$n \mod 4 == 1$ 时，$f(n) = 1$

$n \mod 4 == 2$ 时，$f(n) = n + 1$

$n \mod 4 = 3$ 时，$f(n) = 0$

简化版的代码就更加简洁了，但是记忆难度较大，建议取前几个数自己模拟一下来回忆。

【C++代码】

奇偶讨论版 ✅

#include<bits/stdc++.h>

using namespace std;
typedef long long LL;

// 计算1^2^3...^n（^为异或符号）
LL f(LL n) {
    if (n == 0) return 0;

    // 重要性质：n ^ (n+1) = 1（当n为偶数时均成立）
    // n ^ n = 0（对所有n均成立）
    if (n % 2 == 1) {  // 当前n为奇数
        // 计算1～n中有几对数可以异或成1
        // （1, (2, 3),..., (n-1,n)）
        LL cnt_1 = (n + 1) / 2;
        if (cnt_1 % 2 == 1) return 1;
        else return 0;
    } else {  // 当前n为偶数
        // 计算1～n中有几对数可以异或成1
        // （1, (2, 3),(4, 5)..., (n-2,n-1),n）
        LL cnt_1 = n / 2;
        if (cnt_1 % 2 == 1) return 1 ^ n;
        else return 0 ^ n;
    }
}

int main() {
    LL A, B;
    cin >> A >> B;

    LL res = f(B);
    if (A) res = res ^ f(A - 1);

    cout << res << endl;

    return 0;
}

规律总结版 ✅

#include<bits/stdc++.h>

using namespace std;
typedef long long LL;

// 计算1^2^3...^n（^为异或符号）
LL f(LL n) {
    // 规律总结版
    if (n % 4 == 0) return n;
    else if (n % 4 == 1) return 1;
    else if (n % 4 == 2) return n + 1;
    else if (n % 4 == 3) return 0;
}

int main() {
    LL A, B;
    cin >> A >> B;

    LL res = f(B);
    if (A) res = res ^ f(A - 1);

    cout << res << endl;

    return 0;
}