专栏文章

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

WWide_Master
B4372题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mioidynh
此快照首次捕获于
2025/12/02 19:42
3 个月前
此快照最后确认于
2025/12/02 19:42
3 个月前
查看原文

前言

打表秒出 2n−22^n-2。

正解

我们要想知道 P−QP-Q 的最大值，可以转成求 PP 的最大值和 QQ 的最小值，两者相减即为答案。
我们先来看 QQ 的最小值，从题目可以知道，一个 01 串如果代表的十进制数 CC 如果满足 C≤1C \le 1，那么它的异或之力为 00，而题目有说前导 0 合法，所以我们不难想到，我们可以用 (1)2(1)_2，这样 QQ 最小，即为 00。
再来看 PP 的最大值。容易发现，将这 nn 个数位全都填 11 为最大，易得到答案为 20+21+22+⋯+2n=2n−22^0+2^1+2^2+ \dots +2^n=2^{n}-2。
最后可得到答案为 2n−2−0=2n−22^n-2-0=2^n-2。

代码

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

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...