[luogu] P4144 大河的序列 位运算-证明题

前言

太菜了 传送门: https://www.luogu.com.cn/problem/P4144

思路

本题要求 一个序列里面的 所有数 按位& 之和 和 按位| 之和最大

设 ans 为该序列当前答案 设 x 为需要加进来的数 考虑一下: & 按位且 (只有同时为1 才为1)

ans>x : ans往x那边靠 逐渐变小 ans=x : 肯定是不变的 ans x ： ans可能会变大 但是最高几位没变 但是 按位&会变小 如果ans = x : 不变 如果ans < x : 那么交换一下 直接变成ans>x

因此贪心的猜想一下 答案即等于 maxn+ maxn

code

 #include 
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>x;
        maxn = max(x,maxn);
    }
    
    maxn*=2;
    maxn+=233;
    ll res = qmi(maxn,b,p)%p;
    cout