题解：B4372 [GXPC-S 2025] 异或之力 / xor

weichenglu · 2025-08-11 19:28:09 · 题解

前置芝士

快速幂。

题目概括

给定一个整数 n，考虑所有长度为 n 的 01 字符串（可以包含前导零）。每个字符串对应一个二进制数 C。
对于每个 C，设其异或之力为 a，计算 a：

• 如果 C \le 1，a = 0。
• 如果 C > 1，枚举所有可能的分解方式 A + B = C，并计算：
  • P = \max(A \operatorname{xor} B)
  • Q = \min(A \operatorname{xor} B)
  • a = P - Q

最终，在所有长度为 n 的 01 字符串中，找出最大的 a，并对 10^{9} + 7 取模后输出。

思路分析

通过手玩一些较小的 n，或者 DFS 搜索打表就容易发现这道题的规律。

简单说明：

我们可以从长度为 n 的最大 01 串，2^{n}-1 开始手磨。
但是，2^{n}-1 是不可能成为答案的，虽然异或最大值可以是 2^{n}-1，但是由于其无法分成两个相等的整数，所以异或最小值一定大于 0。
因此，我们尝试 2^{n}-2，其实其就是二进制长度为 n 的最大的偶数。
思考一下：我们要想拆分出来的两个数的异或最大值减去异或最小值最大，那么就要拆分出来的异或最大值尽可能大，最小值尽可能小。异或最大值，可以是这个二进制数本身，因为只需要让每一个二进制位不相同就行；异或最小值可以为 0，因为只需要让每一个二进制位都相同，也就是说两个数相同的时候就行。这样，我们容易发现 2^{n}-2 成为答案是可行的，因为偶数一定可以拆分成两个相同的数，而相同的数异或结果为 0。

综上所述，答案就是 2^{n}-2。

因为 1 \le n \le 10^{9}，需要使用快速幂求解。

注意

1. 我们需要特判当 n=2 的时候，因为 n=2 时，只能分解为 1+1=2，不能分解为 2+0，所以此时答案为 0。
2. 因为在快速幂运行完成后，需要减 2，所以取模时可能出现负数，因此在取模前应先加上模数。
3. 不开 long long 见祖宗！

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;

int n;
const int mod = 1e9+7;

int qpow(int x,int y){
    int res = 1;
    while (y){
        if (y&1) res = res * x % mod;
        x = x * x % mod;
        y >>= 1;
    }
    return res % mod;
}

signed main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n;
    if (n == 2) cout << 0;
    else {
        int ans =  qpow(2,n) % mod - 2;
        if (ans >= 0) cout << ans;
        else cout << ans + mod;
    }

    return 0;
}

总结

一道诈骗题偏思维题。