题解 P4144 【大河的序列】

xzyxzy · 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;
}