[luogu] P4144 大河的序列 位運算-證明題

前言

太菜了

傳送門: https://www.luogu.com.cn/problem/P4144

思路

本題要求 一個序列裡面的 所有數 按位& 之和 和 按位| 之和最大

設 ans 為該序列目前答案

設 x 為需要加進來的數

考慮一下:

& 按位且 (隻有同時為1 才為1)

ans>x : ans往x那邊靠 逐漸變小

ans=x : 肯定是不變的

ans<x : ans逐漸往x 那邊靠 逐漸變大

(是以大&小 隻會讓大的變小)

| 按位或(隻要有1就是1)

如果ans > x ： ans可能會變大 但是最高幾位沒變 但是 按位&會變小

如果ans = x : 不變

如果ans < x : 那麼交換一下 直接變成ans>x

是以貪心的猜想一下 答案即等于 maxn+ maxn

code

#include <bits/stdc++.h>
using namespace std;

using ll  = long long ;

ll qmi(ll a,ll b,ll m)
{
     a%=m;
    ll res=  1;
    while(b>0)
    {
        if(b&1) res = res * a % m;
        a = a*a%m;
        b>>=1;
    }
    return res;

}
void solve()
{
    ll n,b,p;
    cin>>n>>b>>p;
    ll maxn = 0 ;
    for(ll i=1; i<=n; i++)
    {
        ll x;
        cin>>x;
        maxn = max(x,maxn);
    }
    
    maxn*=2;
    maxn+=233;
    ll res = qmi(maxn,b,p)%p;
    cout<<res<<endl;
}
signed main()
{
    ios::sync_with_stdio(false);
    solve();
    return 0;
}