题解：B4372 [GXPC-S 2025] 异或之力 / xor
Link
假设某个 01 字符串所代表的十进制数为 \(C\)，当 \(C \le 1\) 时异或之力为 \(0\)；当 \(C > 1\) 时，将 \(C\) 分解成任意两个正整数 \(A\) 和 \(B\) （\(A > 0\)，\(B > 0\)，\(A + B = C\)），得到 \(A\) 异或 \(B\) 的最大值为 \(P\)，异或最小值为 \(Q\)，异或之力即为 \(P\) 和 \(Q\) 的差值。
题目思路
设异或之力为 \(f\)，则 \(f=P-Q=(A \oplus B)_{\max}-(A \oplus B)_{\min}\)。
首先我们想到，对于一个 \(n\) 位的二进制串，要使其十进制状态下最大，显然有这样一个字符串：
设这个二进制串在十进制下的值为 \(g(n)\)，则 \(g(n)=2^{n}-1\)。
考虑最大值。根据异或的性质，有 \(A+B=n\) 且 \(A \oplus B = n\)。因此必然有 \(A \oplus B \le n\)。因此最大值为 \(g(n)=2^{n}-1\)。
考虑最小值。因为 \(2^n \bmod 2=0\)，所以 \(2^{n}-1 \bmod 2 \neq 0\)。所以当 \(A \oplus B=g(n)\) 时，一定有 \(A \neq B\)，因此 \((A \oplus B)_{\min}=1\)。
此时 \(f=(A \oplus B)_{\max}-(A \oplus B)_{\min}=2^{n}-1-1=2^{n}-2\)。
考虑是否最优。令 \(g(n)=2^{n}-2\)，则 \(g(n) \bmod 2=0\)，此时 \((A \oplus B)_{\max}=g(n)=2^{n}-2\)，\((A \oplus B)_{\min}=0\)，此时 \(f=(A \oplus B)_{\max}-(A \oplus B)_{\min}=2^{n}-2-0=2^{n}-2\)。
令 \(g(n)=2^{n}-3\)，则 \(g(n) \bmod 2 \neq 0\)，此时 \((A \oplus B)_{\max}=g(n)=2^{n}-3\)，\((A \oplus B)_{\min}=1\)，此时 \(f=(A \oplus B)_{\max}-(A \oplus B)_{\min}=2^{n}-3-1=2^{n}-4\)。
所以我们可以得出，当 \(g(n) < 2^n-1\) 时，\(f \le 2^{n}-1\)。
证毕，所以 \(f=2^{n}-1\)。
注意 \(n=2\) 时，最大值和最小值的取值方法都是相同的，此时 \(f=0\)。
考虑到 \(2 \le n \le 10^{9}\)，这里使用快速幂。
代码实现
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD=1e9+7;
ll n;
inline ll qp(ll a,ll b,ll mod){ll ans=1;a%=mod;while(b){if(b&1) ans=(ans)*a%mod;a=a*a%mod,b>>=1;}return ans;
}
int main(){cin>>n;if(n==2){cout<<0;return 0;}cout<<(qp(2,n,MOD)-2+MOD)%MOD;return 0;
}