题解 P4144 【大河的序列】

### 答案是最大的那个数乘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 ```cpp // 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](https://www.cnblogs.com/xzyxzy)