题解：P17766 「LDOI R2」位运算 / Bit
SBro
·
·
题解
前言：赛时被卡常，赛后 3 min AC。（悲）
思路：
考虑拆位贡献。
我们先只考虑 x 与 y 的影响，不考虑 z。
令 x_i 为 x 在二进制下的第 i 位，y,z,a_{idx} 同理。
对于 a_i 的第 j 位：
- 若 x_j 为
1 则 a_{i,j} 必为 1。
- 若 x_j 不为
1 但 y_j 为 1，则对于每个 a_i，至少有一个当前位数为 0，至少有一个当前位数为 1，其余任定（选 0 选 1 均可）。
- 若 x_j, y_j 均不为
1，则 a_{i,j} 必为 0。
- 若 x_j 为
1 但 y_j 为 0，则无解。
现在考虑 z 的限制。
由于我们要最大化答案，因此对于 a_i 的每一位，1 的个数应尽可能的多。
我们可以先确定第 i 列的 1 的个数 c_i。
对于 z 的每一位：
- 当 z_j = 1 时：
- 若 x_j = 1，则必定有 a_{i,j} = 1，我们只需考虑是否合法即可。
考虑 n 的奇偶性。
由于异或的性质，偶数个相同数字的异或和为
0，故当 n 为奇数时有解，c_j = n，否则无解。
- 若 x_j = 0 且 y_j = 1，则我们要保证至少有一个
0 的出现。
当 n 为奇数时，需要两个 0 以保证异或和合法，否则只需一个 0 即可。
此时等价于 1 的出现次数分别为 n-2，n-1 个。
即 c_j = n-2（n \equiv 1 \pmod 2） 或 c_j = n-1（n \equiv 0 \pmod 2）。
- 若 x_j = 0 且 y_j = 0，此时所有 a_{i,j} = 0，但有 z_j = 1，矛盾，故无解。
- 当 z_j = 0 时：
- 若 x_j = 1，则必定有 a_{i,j} = 1，此时该列的异或和等于 n 个
1 的异或和。
当 n 为偶数时，异或和为 0，合法，此时 c_j = n；
当 n 为奇数时，异或和为 1，与 z_j = 0 矛盾。
因此 n 为奇数时无解，n 为偶数时无需额外处理。
- 若 x_j = 0 且 y_j = 1，则我们要保证至少有一个
0 的出现，并使其异或和为 0。
当 n 为奇数时，0 的出现次数取 1 即可；当 n 为偶数时，0 的出现次数取 2 即可。
此时等价于 1 的出现次数分别为 n-1，n-2 个。
即 c_j = n-1（n \equiv 1 \pmod 2） 或 c_j = n-2（n \equiv 0 \pmod 2）。
- 若 x_j = 0 且 y_j = 0，此时没有强制约束，可令该列全为
0，异或和自然为 0，故无需额外处理。
此时 c_j = n。
如何分配这些 1 使得乘积最大
假设当前两个数的已有值为 A\le B，这一位需要给其中一个数加上 2^i。比较两种选择：
给 A 加：(A+2^i)B；
给 B 加：A(B+2^i)。
两者相减：
所以给较小的 $A$ 加这一位不会更劣。
因此最优策略是：
从高位到低位处理，对于第 $i$ 位，把这一位的 $1$ 分给当前值**最小**的 $c_i$ 个数。
等价地，可以先把这一位默认分给所有数，再从当前值最大的 $n-c_i$ 个数中删掉这一位。
注意到对于合法的 $c_i$，只有如下四种值：
$$
0, n-2, n-1, n
$$
则 $(n-c_i) \in \{ n,2,1,0 \}$。
而对于 $n-c_i = n,0$ 而言，并不影响相对大小。
故可以使用**分组**和**优先队列**维护。
具体地，把当前值相同的数合并成一组，记为 $(rel, c)$。
- $\mathrm{rel}$：这一组相对于公共基准值 $\mathrm{base}$ 的偏移；
- $c$：这一组有多少个数。
初始时所有数都是 $0$，所以堆中只有 $(0,n)$。
处理第 $i$ 位时：
若 $c_i=0$，这一位没有数取 $1$，直接跳过。
否则先把这一位默认分给所有数：$\mathrm{base}\mathrel{+}=2^i$。
需要从当前值最大的 $k=n-c_i$ 个数中删掉这一位。
- 若 $c_i=n$，则 $k=0$，不用删；
- 若 $c_i=n-1$，则 $k=1$；
- 若 $c_i=n-2$，则 $k=2$。
从大根堆中取出 $\mathrm{rel}$ 最大的组，把其中 $k$ 个数的 $\mathrm{rel}$ 减去 $2^i$。如果组大小大于 $k$，则分裂成两组；否则整组修改后放回。
最后堆中每一组 $(\mathrm{rel},c)$ 对应 $c$ 个相同的数：
$$
\mathrm{value}=\mathrm{base}+\mathrm{rel}
$$
答案就是：
$$
\prod (\mathrm{base}+\mathrm{rel})^{c} \pmod{998244853}
$$
设二进制位数为 $B \le 60$，则时间复杂度为 $O(T(B \log B + B \log n))$。
::::success[Code]
```cpp
#include <bits/stdc++.h>
#define ll long long
#define pll pair<ll, ll>
#define ld long double
#define ull unsigned ll
#define pull pair<ull, ull>
#define il inline
using namespace std;
char buf[1<<20], *p1, *p2;
char gc() {
if(p1 == p2) p2 = (p1 = buf) + fread(buf, 1, 1<<20, stdin);
return *p1++;
}
ull read() {
ull s = 0;
char c = gc();
while(c < 48) c = gc();
while(c > 47) s = s * 10 + (c ^ 48), c = gc();
return s;
}
il void wrt(ll x) {
if(x == 0) { putchar('0'); return; }
if(x < 0) { putchar('-'); x = -x; }
char buf[24];
int len = 0;
while(x > 0) {
buf[len++] = char('0' + x % 10);
x /= 10;
}
while(len > 0) putchar(buf[--len]);
}
const ll mod = 998244853;
il ll qpow(long long a, long long b) {
a %= mod;
ll res = 1;
while(b > 0) {
if(b & 1) res = (res * a) % mod;
a = (a * a) % mod;
b >>= 1;
}
return res;
}
int main() {
ll T = read();
while(T--) {
ll n = read(), x = read(), y = read(), z = read();
bool ok = 1;
ll cnt[63] = {};
for(int i = 0; i <= 61; ++i) {
bool X = (x >> i) & 1;
bool Y = (y >> i) & 1;
bool Z = (z >> i) & 1;
if(X && !Y) {
ok = 0;
break;
}
if(Z) {
if(X) {
if((n & 1) == 0) {
ok = 0;
break;
}
cnt[i] += n;
} else if(Y) {
ll val = (n - 1 - (n & 1));
if(val < 1) {
ok = 0;
break;
}
cnt[i] += val;
} else {
ok = 0;
break;
}
} else {
if(X) {
if(n & 1) {
ok = 0;
break;
}
cnt[i] += n;
} else if(Y) {
ll val;
if(n & 1) val = n - 1;
else val = n - 2;
if(val < 1) {
ok = 0;
break;
}
cnt[i] += val;
}
}
}
if(!ok) {
wrt(-1);
putchar('\n');
continue;
}
priority_queue<pll> q; // 最大堆 (rel, cnt)
q.push({0, n});
ll base = 0;
for(int i = 61; i >= 0; --i) {
ll need = cnt[i];
ll k = n - need;
if(k == n) continue; // 所有数都不加这一位
base += (1ll << i); // 默认所有数加这一位
vector<pll> tmp;
while(k > 0 && !q.empty()) {
auto [rel, c] = q.top();
q.pop();
if(c > k) {
tmp.push_back({rel, c - k});
tmp.push_back({rel - (1LL << i), k});
k = 0;
} else {
tmp.push_back({rel - (1LL << i), c});
k -= c;
}
}
for(auto p : tmp) q.push(p);
}
ll ans = 1;
while(!q.empty()) {
auto [rel, c] = q.top();
q.pop();
ll real = base + rel;
real %= mod;
if(c == 1) {
ans = ans * real % mod;
} else {
ans = ans * qpow(real, c) % mod;
}
}
wrt(ans);
putchar('\n');
}
return 0;
}
```
::::