自动搬运

查看原文

来自洛谷，原作者为

	xzyxzy 被pku里高三的巨佬们虐惨了啊啊啊啊

搬运于2025-08-24 21:56:59，当前版本为作者最后更新于2018-06-30 08:11:16，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

答案是最大的那个数乘2

证明

假设现在答案是w，加入一个数x，依照按位贪心的思想（选高位的1一定最优），分两种情况讨论：

1.w>x w在前面的位上有1但x没有，那么肯定不选x，因为&和损失的高位上的1,再怎么增加|和的后面位置的1都于事无补,那么这个时候选w优于选wx优于选x

2.w=x 显然这时选不选都没关系

3.w<x w前几位的1,x都有，而且w某一个较高位的0,x也有1,这个时候如果把w与x合并，只会增加|和，而如果抛弃w把答案置为x，那么会增加|和和&和，显然这时选x更优，其实就是swap(x,w)就转化成了第一种情况

综上，答案是最大的数乘2

// luogu-judger-enable-o2
#include<iostream>
using namespace std;
int n,b,p,mod;
int ksm(int x,int k)
{
    int ans=1,base=x;
    while(k)
    {
        if(k&1) ans=1ll*ans*base%mod;
        base=1ll*base*base%mod; k>>=1;
    }
    return ans;
}
int main()
{
    cin>>n>>b>>mod;
    for(int i=1,x;i<=n;i++) cin>>x,p=max(x,p);
    cout<<ksm(p*2+233,b)%mod;
}

Advertisement