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

前置芝士

题目概括

给定一个整数

n

，考虑所有长度为

n

的 01 字符串（可以包含前导零）。每个字符串对应一个二进制数

C

。
对于每个

C

，设其异或之力为

a

，计算

a

：

如果 $C \le 1$ ， $a = 0$ 。
如果 $C > 1$ $C > 1$ ，枚举所有可能的分解方式 $A + B = C$ $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}

，需要使用快速幂求解。

注意

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

代码

CPP

#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;
}

总结

一道~~诈骗题~~偏思维题。

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

文章操作

前置芝士

题目概括

思路分析

简单说明：

注意

代码

总结

相关推荐

评论

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