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

· · 题解

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

思路

由于位运算的每一位是互相独立的，因此我们不妨从高位到低位枚举 b=59\dots 0，分别记 x, y, z 对应的 x_b, y_b, z_b 为 x, y, z 右移 b 位再按位与 1。

我们先判断这一位是否有解，再考虑如何分配才能让乘积最大。

如果 x_b=1，说明与运算该位为 1，也就是所有 n 个数的这一位都必须是 1。于是或运算该位必为 1，异或运算该位等于 n 个 1 异或，即 n\bmod 2。因此必须满足 y_b=1 且 z_b=n\bmod 2，否则直接无解。

如果 x_b=0 且 y_b=0，说明或运算该位为 0，也就是所有数这一位都是 0。此时异或位必然是 0，所以 z_b 必须为 0，否则无解。

我们发现只有 x_b=0,y_b=1 可以选，这一位不能全为 1 或 0。设有 d 个数这一位取 0，则 1\le d\le n-1，而异或位等于 (n-d)\bmod 2，即 d\bmod 2=(n\bmod 2)\oplus z_b。

为了让乘积尽量大，我们当然希望取 0 的数尽量少，因为每多一个取 0 的数，就相当于让某个数少掉 2^b。于是令 t=(n\bmod 2)\oplus z_b，它就是 d 的奇偶性要求。若 n=1，这一位不可能既满足与为 0 又满足或为 1，无解。若 n=2，只能一个取 1 一个取 0，所以必须 t=1，即 z_b=1，否则无解，此时 d=1。若 n>2，则当 t=1 时取最小 d=1，当 t=0 时取最小 d=2。记这个最小需要取 0 的个数为 m，它只会是 1 或 2。

注意到或运算为 y，所以每个 a_i 都必然是 y 的子集。对于 x_b=1 的位，所有数都必须保留；对于 x_b=0,y_b=0 的位，所有数都没有这一位。

只有那些 x_b=0,y_b=1 的位可以，这些位在 y 中是 1，我们需要在其中 m 个数里把它变成 0。

于是我们先假设所有数都等于 y，然后对于每个位 b，我们需要选出 m 个不同的数，把这些数的第 b 位从 1 改成 0。记第 i 个数被删掉的位权之和为 h_i，那么最终 a_i=y-h_i。

我们要最大化的是 \prod_{i=1}^n (y-h_i)。

还没有被删过任何位的数，其 h_i=0，最终值为 y。

对于每个关键位，它的权值是 w=2^b，需要给 m 个不同的数各加上 w。考虑函数 f(h)=\ln(y-h)。

在 h<y 的范围内它是凹函数，二阶导数为负，这意味着把同样的增量分散到多个数上，比集中到少数数上更优；而在必须选择哪些数接收增量时，应该优先选择当前 h 较小的数。

举个例子，假设 h_a\le h_b，如果把这 w 加给 b 而不给 a，乘积是 (y-h_a)(y-h_b-w)；如果加给 a 而不给 b，乘积是 (y-h_a-w)(y-h_b)。两者之差为 w\big((y-h_a)-(y-h_b)\big)\ge 0。

所以把减量加给当前 h 更小的数一定不会更差。这就给出了贪心策略：每次处理一个关键位时，总是选择当前 h 最小的 m 个数，让它们各自加上 w。

由于我们是从高位到低位处理，权值 w 依次减半，而每个数的 h 只增不减，所以可以用一个小根堆维护所有 h_i>0 的数，同时用 k 表示还没有被删过位的“空数”个数，也就是 h_i=0 的数的数量。

对于 m=1 的情况，如果 k>0，直接拿出一个空数，把它的 h 设为 w，并让 k 减一；否则说明所有数都已经被删过位了，就取出堆顶的最小 h，把它改成 h+w 再放回去。

对于 m=2 的情况，如果 k\ge 2，用两个空数，分别放入 w；如果 k=1，用一个空数放入 w，再取堆顶的 h 改成 h+w，同时 k 归零；如果 k=0，就取出堆顶的两个 h_1,h_2，分别改成 h_1+w 和 h_2+w 放回去。

所有位处理完之后，堆中的每个 h_i 对应一个因子 y-h_i，而剩下的 k 个空数对应的因子都是 y。于是答案就是

\left(\prod (y-h_i)\right)\cdot y^k \pmod{998244853}

如果中途任何一位判定无解，直接输出 -1。

代码

::::success[代码]

#include <bits/stdc++.h>
#define endl '\n'
#define MOD 998244853
#define int unsigned long long
using namespace std;

int sz, cnt, tot;
int bits[65], ms[65], hp[205];

void push(int v)
{
    hp[++sz] = v;
    int i = sz;
    while (i > 1 && hp[i] < hp[i / 2])
    {
        swap(hp[i], hp[i / 2]);
        i /= 2;
    }
}

void pop()
{
    hp[1] = hp[sz--];
    int i = 1;
    while (1)
    {
        int l = i * 2, r = l + 1, mid = i;
        if (l <= sz && hp[l] < hp[mid])
            mid = l;
        if (r <= sz && hp[r] < hp[mid])
            mid = r;
        if (mid == i)
            break;
        swap(hp[i], hp[mid]);
        i = mid;
    }
}

int qpow(int a, int b)
{
    long long c = a % MOD, res = 1;
    while (b)
    {
        if (b & 1)
            res = res * c % MOD;
        c = c * c % MOD;
        b >>= 1;
    }
    return res;
}

char buf[1 << 20], *p1, *p2;
char gc()
{
    if (p1 == p2)
        p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin);
    return *p1++;
}

int rd()
{
    int s = 0;
    char c = gc();
    while (c < 48)
        c = gc();
    while (c > 47)
        s = s * 10 + (c ^ 48), c = gc();
    return s;
}

int T, n, k, x, y, z, f, ans;

void mian()
{
    n = rd(), x = rd(), y = rd(), z = rd(), f = 1;
    cnt = tot = sz = 0, k = n, ans = 1;
    for (signed b = 59; b >= 0; b--)
    {
        int xb = (x >> b) & 1, yb = (y >> b) & 1, zb = (z >> b) & 1;
        if (xb)
        {
            if (!yb || zb != (n & 1))
            {
                f = 0;
                break;
            }
        }
        else if (yb)
        {
            if (n == 1)
            {
                f = 0;
                break;
            }
            int t = (n & 1) ^ zb, m;
            if (n == 2)
            {
                if (t != 1)
                {
                    f = 0;
                    break;
                }
                m = 1;
            }
            else
                m = 1 + (t == 0);
            bits[++cnt] = b;
            ms[cnt] = m;
            tot += m;
        }
        else if (zb)
        {
            f = 0;
            break;
        }
    }
    if (!f)
        return cout << -1 << endl, void();
    for (int i = 1; i <= cnt; i++)
    {
        int w = 1ULL << bits[i];
        int m = ms[i];
        if (m == 1)
        {
            if (k > 0)
            {
                k--;
                push(w);
            }
            else
            {
                int h = hp[1];
                pop();
                push(h + w);
            }
        }
        else
        {
            if (k >= 2)
            {
                k -= 2;
                push(w);
                push(w);
            }
            else if (k == 1)
            {
                k = 0;
                int h = hp[1];
                pop();
                push(w);
                push(h + w);
            }
            else
            {
                int h1 = hp[1];
                pop();
                int h2 = hp[1];
                pop();
                push(h1 + w);
                push(h2 + w);
            }
        }
    }
    for (int i = 1; i <= sz; i++)
        ans = ans * ((y - hp[i]) % MOD) % MOD;
    ans = ans * qpow(y % MOD, k) % MOD;
    cout << ans << endl;
}
signed main()
{
    T = rd();
    while (T--)
        mian();
    return 0;
}

::::