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

· · 题解

前言

打表秒出 2^n-2。

正解

我们要想知道 P-Q 的最大值，可以转成求 P 的最大值和 Q 的最小值，两者相减即为答案。

我们先来看 Q 的最小值，从题目可以知道，一个 01 串如果代表的十进制数 C 如果满足 C \le 1，那么它的异或之力为 0，而题目有说前导 0 合法，所以我们不难想到，我们可以用 (1)_2，这样 Q 最小，即为 0。

再来看 P 的最大值。容易发现，将这 n 个数位全都填 1 为最大，易得到答案为 2^0+2^1+2^2+ \dots +2^n=2^{n}-2。

最后可得到答案为 2^n-2-0=2^n-2。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=1e9+7;
int n;
int power(int a,int b){
    int res=1;
    while(b){
        if(b&1)res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}
signed main()
{
    cin>>n;
    if(n==2){cout<<0<<endl;return 0;}
    cout<<(power(2,n)-2+mod)%mod<<endl;
    return 0;
}