题解：P17766 「LDOI R2」位运算 / Bit

梦见云月 · 2026-10-24 20:57:02 · 题解

首先有一些明显的特判，就是根据 x,y,z 相对关系找有没有矛盾。

思考哪些位置我们不确定，发现是二进制下 x 为 0 但 y 为 1 的位置。

根据 z 的相关异或结果以及 n 的奇偶性，我们也可以知道这一位 1 的个数的奇偶性，贪心的考虑，要尽量的多。

然后是分配这些缺口，有一个贪心就是尽量均衡的分配，感性思考就是经典的 x^2>(x+d)(x-d)，大概是这么个类似物。

如果 n 够大，每个分配给一个就好，如果不是，就要每次从大到小挑选缺口，挑选缺口最少的加上。

由于缺口不会很多，后者可以直接暴力。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=998244853;

int n,x,y,z;
int s[1000005];
int lst[1005];

inline int ksm(int a,int x){
    a%=mod; 
    int res=1;
    while (x){
        if (x&1){
            res=res*a%mod;
        }
        a=a*a%mod;
        x>>=1;
    }
    return res;
}


vector<pair<int,int> > vec;

inline void solve(){
    cin>>n>>x>>y>>z;
    if ((x&y)!=x){
        cout<<"-1\n";
        return;
    }
    if ((n&1) && ((x&z)!=x)){
        cout<<"-1\n";
        return;
    }
    if (!(n&1) && (x&z)){
        cout<<"-1\n";
        return;
    }
    if ((~y)&z){
        cout<<"-1\n";
        return;
    }
    int w=(~x)&y;
    if (!w){
        cout<<ksm(x,n)<<'\n';
        return;
    }
    if (n==1){
        cout<<"-1\n";
        return;
    }
    vec.clear();
    for (int i=0;i<60;i++){
        if (w>>i&1ll){
            int ww=(z>>i)&1ll;
            int op=(n&1)^ww;
            int t;

            if (op==1){
                t=1;
            }
            else{
                t=2;
            }
            if  (t>=n){
                cout<<"-1\n";
                return;
            }
            for (int j=0;j<t;j++){
                vec.push_back(make_pair((1ll<<i),i));
            }
        }
    }
    int len=vec.size();
    sort(vec.begin(),vec.end());
    reverse(vec.begin(),vec.end());
    if (n>=len){
        int ans=ksm(y,n-len);
        for (int i=0;i<len;i++){
            int ww=vec[i].first;
            ans=(y%mod-ww%mod+mod)%mod*ans%mod; 
        }
        cout<<ans<<'\n';
    }
    else{
        for (int i=0;i<=n;i++){
            s[i]=0;
        }
        for (int i=0;i<=70;i++){
            lst[i]=-1;
        }
        for (int i=0;i<len;i++){
            int ww=vec[i].first;
            int id=vec[i].second;
            int pos=-1;
            for (int j=0;j<n;j++){
                if (j==lst[id]){
                    continue;
                }
                if (pos==-1 || s[j]<s[pos]){
                    pos=j;
                }
            }
            lst[id]=pos;
            s[pos]+=ww;
        }
        int ans=1;
        for (int i=0;i<n;i++){
            ans=(y%mod-s[i]%mod+mod)%mod*ans%mod;
        }
        cout<<ans<<'\n';
    }

    return;
}
int T;
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>T;
    while (T--){
        solve();
    }
    return 0;
}