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

_Weslie_ · 2026-10-24 20:01:27 · 题解

这是啥？青吗？

首先显然拆位考虑。

判断无解

以下情况很显然无解：

接下来枚举位，假设 x,y,z 第 i 位分别为 a,b,c，那么：

若 a=1：
- 若 b=0，显然不会有 n 个数字出现与结果为 1，或结果为 0 的情况，直接输出 -1。
- 若 c\ne n\bmod 2，由于全部数这一位都要为 1，那么 c 理论应该与 n\bmod 2 相等，此时我们应该判掉。
若 b=0：
- 若 c=1：b=0 时所有这一位都是 0，因此不可能出现 c=1。判掉。

记录每一位有多少个 1

很显然，这些数的总和越大，这些数的积的最大值就越大。因此我们考虑让一位上尽可能多的数为 1。

我们考虑分讨：

若 a=1，那么这一位有 n 个 1。
若 b=0，那么这一位有 0 个 1。
若 c=1：
- 若 n 为奇数，那么最多有 n-2 个 1。这里要把 n=1 判掉。
- 若 n 为偶数，那么最多有 n-1 个 1。
若 c=0：
- 若 n 为偶数，那么最多有 n-2 个 1。
- 若 n 为奇数，那么最多有 n-1 个 1。

贪心求积的最大值

学过高中数学必修一的同学一定知道这个不等式：

a+b\ge 2\sqrt{ab}

事实上，对 n 个正整数 a_1,a_2,\cdots,a_n，有：

\dfrac{\sum\limits_{i=1}^na_i}{n}\ge \sqrt[n]{\prod_{i=1}^na_i}

考虑如何证明它：

::::success[证明] 设 f(x)=\ln x，有

f^{\prime}(x)=\dfrac{1}{x}\\f^{\prime\prime}(x)=-\dfrac{1}{x^2}<0

由高中数学选择性必修 2 知，二阶导小于 0，函数图像上凸。

所以有：

\begin{aligned} ln(\dfrac{a_1+a_2+\cdots+a_n}{n})=f(\dfrac{a_1+a_2+\cdots+a_n}{n})&\ge f(a_1)+f(a_2)+\cdots+f(a_n)\\\ &=\ln a_1+ln a_2+\cdots \ln a_n\\ &=\ln (a_1a_2\cdots a_n) \end{aligned}

所以

\dfrac{a_1+a_2+\cdots+a_n}{n}\ge a_1a_2\cdots a_n

::::

而该不等式取等的条件是 a_1=a_2=\cdots a_n，这启示我们要让 a_i 尽可能平均。

所以我们按位从高到低贪心，假设这一位有 k 个 1，每一次我们取前 k 小的给它这一位赋值为 1 即可。复杂度 O(Tn\log V\log n)。

但是我们发现 k 具有性质：根据上面的讨论，k\in\{n,n-1,n-2\}，因此 n-k\in \{0,1,2\}。于是我们可以把它改成这样的贪心：

设极大值 mx=2^{60}-1。

按位从高到低贪心，先把所有数都赋值为极大值，假设这一位有 k 个 1，每一次我们取前 n-k 大的给它这一位赋值为 0 即可。复杂度 O(T\log V\log n)。

阈值 120

但是显然 n 可能很大，此时过不去。我们考虑分讨。

我们考虑当 n 特别之大时，贪心过程是这样的：

我们选出来前 k 大，显然因为 n 足够大，所以全是极大值。
我们把这些极大值的第 i 位扣掉。
因为第 i 位被设置为 0 了，所以它不再是极大值，不可能再次把它的一位设置为 0。

也就是说我们构造出的数列每一个数都是 mx-2^i 的形式，由于 \log V 比较小，我们可以直接枚举第 i 位形成了多少个这样的数，然后乘进去。其他的全部都是极大值，用快速幂解决即可。

由于最多有 60 位，k\le 2，所以只要 n\ge 120，就一定可以满足这种情况。

那么上面情况的 n 最大就是 120 而不是 2^{60}-1 了，就能过了。

复杂度 O(T(\log V\log l+\log V))，其中 l=120。

实测 1.99 秒过，要卡常。

::::success[Code]


#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define i128 __int128
#define Nos puts("-1");return;
ll n,x,y,z;
const int N=61,mod=998244853;
int a[N],b[N],c[N],d[N];
int f[N];
ll p[10005],tmp[135];
priority_queue<ll>q;
ll qpow(ll a,ll b){
    ll res=1;
    while(b){
        if(b&1)res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}
typedef unsigned long long ull;
char buf[1<<20],*p1,*p2;
char gc() {
    if(p1==p2) p2=(p1=buf)+fread(buf,1,1<<20,stdin);
    return *p1++;
}
ull rd() {
    ull s=0;
    char c=gc();
    while(c<48) c=gc();
    while(c>47) s=s*10+(c^48), c=gc();
    return s;
}
void solve(){
    n=rd();x=rd();y=rd();z=rd();
    if(n==1&&x!=y){
        puts("-1");return;
    }
    for(ll i=0;i<=59;i++){
        a[i]=((x>>i)&1);
        b[i]=((y>>i)&1);
        c[i]=((z>>i)&1);
    }
    ll ans=0;
    memset(d,0,sizeof d);
    for(int i=0;i<=59;i++){
        if(a[i]==1){
            if(c[i]!=(n&1)){
                puts("-1");return;
            }
            if(b[i]==0){
                puts("-1");return;
            }
            d[i]=n;
            continue;
        }
        if(b[i]==0){
            if(c[i]==1){
                puts("-1");return;
            }
            d[i]=0;
            if(a[i]==1){
                puts("-1");
                return;
            } 
            continue;
        }

        if(a[i]==1||b[i]==0)continue;
        if(c[i]==1){
            if(n&1){
                if(n<=1){
                    puts("-1");return;
                }
                d[i]=n-2; 
            }
            else {
                d[i]=n-1;
            }
        }
        else{
            if((n+1)&1){
                if(n<=1){
                    puts("-1");return;
                }
                d[i]=n-2;
            }
            else {
                d[i]=n-1;
            }
        }
    }
    int r=0;
    ll t=0;
    for(int i=0;i<=59;i++){
        if(d[i]!=0){
            if(d[i]!=n)f[i]=n-d[i];
            else f[i]=-1;
            t+=(1ll<<i);
        }
        else{
            f[i]=-1;
        }
        if(f[i]!=-1)r+=f[i];
    }
    if(n>=120){
        ll suu=1;
        for(int i=0;i<=59;i++){
            if(f[i]!=-1){
                if(f[i]==1)suu=suu*((t-(1ll<<i))%mod)%mod;
                else if(f[i]==2){
                    suu=suu*((t-(1ll<<i))%mod)%mod;
                    suu=suu*((t-(1ll<<i))%mod)%mod;
                }
            }
        }
        suu=suu*qpow(t%mod,n-r)%mod;
        printf("%lld\n",suu);
        return;
    }
    while(!q.empty())q.pop();
    for(int i=1;i<=n;i++)q.push(t);
    int leN=0;
    for(int i=59;i>=0;i--){
        int t=0;
        leN=0;
        if(f[i]==-1)continue;
        while(!q.empty()){
            t++;
            tmp[++leN]=q.top();
            q.pop();
            if(t==f[i])break;
        }
        for(int j=1;j<=leN;j++){
            tmp[j]-=(1ll<<i);
            q.push(tmp[j]);
        }
    }
    ll sum=1;
    int len=0;
    while(!q.empty()){
        p[++len]=q.top();
        sum*=(p[len]%mod);sum%=mod;
        q.pop();
    }
    ll uu=(1ll<<60)-1,vv=0,ww=0;
    for(int i=1;i<=n;i++){
        uu=uu&p[i];vv=vv|p[i];ww=ww^p[i];
    }
    if(uu!=x||vv!=y||ww!=z){
        puts("-1");return;
    }
    printf("%lld\n",sum);
}
int main(){
    int T;T=rd();
    while(T--)solve();
}
::::