Two language versions are available in order to serve both codeforces and luogu community.
English Version
Hints
-
What's the necessary condition for \(a_1^\prime\&a_2^\prime\cdots\&a_n^\prime=X\) to hold?
-
How can we ensure \(a_1^\prime\&a_2^\prime\cdots\&a_n^\prime\) is exactly equal to \(X\)?
-
Pay attention to some corner cases.
-
How can we optimize the procedure?
Solution
Step 1
We begin by considering a straightforward \(O(nq)\) approach.
A necessary condition for \(a_1^\prime\&a_2^\prime\cdots\&a_n^\prime=X\) to hold is that each modified value \(a_i^\prime\) must satisfy \(a_i^\prime\&X=X\).
So define \(up_X(a_i)\) is the minimum non-negative integer such that \((a_i+up_X(a_i))\&X=X\). Let \(b_i=a_i+up_X(a_i)\). To compute \(up_X(x)\),we locate the highest bit \(B\) (if any) where the binary representations of \(x\) and \(X\) differ.Then set it to \(1\) and keep the lower bits conform to \(X\).
After adjustment,let \(Y=b_1\&b_2\cdots\&b_n\). It satisfies that \(Y\&X=X\).
Next, we need to ensure that \(Y\) is exactly equal to \(X\). Similarly, locate the highest bit \(B\) (if any) and turn it to \(0\). If \(b_k\) is modified to turn \(B\) bit to \(0\). It can be shown that optimally, only one operation on a single element is sufficient to correct all lower differing bits as well.
When \(n\ge 2\), a potential issue arises: if we modify \(b_k\) on a bit where every element except \(b_k\) is \(1\) , \(Y\neq X\) again. To avoid this, it is generally optimal to operate on an element other than the one that would cause such a conflict.
Based on this, we can easily write a \(O(nq)\) code and submit.
Code for reference.
Step 2
After we get \(Y\), we try to speed up the procedure.
Let the bits of \(X\) be denoted as \(x_1,x_2\cdots x_k\) in descending order.
We process the bits from the highest to the lowest. At the \(i\)-th time,all \(a_i\) which contains \(x_1,x_2\cdots,x_{i-1}\) but not \(x_i\) are processed. It can be calculated by AND Fast Walsh-Hadamard Transform (FWT) and the Principle of Inclusion-Exclusion (PIE).
Code for reference.
Step 3
To make \(Y\) exactly \(X\), we identify the highest bit \(B\) where \(X\) and \(Y\) differ. We then look for an element \(a_k\) such that modifying it minimizes the number of operations required and it won't add new bits to \(Y\).
Let \(b\) be the highest bit changed in Step 2. We enumerate \([b+1,20]\). If at digit \(i\), \(0\) exists at least twice,find the number with
with the largest value in the lower \(i\) bits (i.e. \(a_k\&(2^i-1)\)) and compute it in \(O(1)\) time.
Note the special case where \(X=Y\).
Code for reference.
中文版本
Hint
• 要使 \(a_1^\prime\&a_2^\prime\cdots\&a_n^\prime=X\) 成立的必要条件是什么？
• 如何确保 \(a_1^\prime\&a_2^\prime\cdots\&a_n^\prime\) 恰好等于 \(X\)？
• 注意一些边界情况。
• 如何加速操作过程？
Solution
Step 1
我们首先考虑一个直接的 \(O(nq)\) 方法。
要使 \(a_1^\prime\&a_2^\prime\cdots\&a_n^\prime=X\) 成立的一个必要条件是每个修改后的值 \(a_i^\prime\) 必须满足 \(a_i^\prime\&X=X\)。
因此定义 \(up_X(a_i)\) 是满足 \((a_i+up_X(a_i))\&X=X\) 的最小非负整数。令 \(b_i=a_i+up_X(a_i)\)。为了计算 \(up_X(x)\)，我们找到 \(x\) 和 \(X\) 的二进制表示中不同的最高位 \(B\)（如果存在）。然后将其设置为 \(1\)，并将低位调整为符合 \(X\)。
调整后，令 \(Y=b_1\&b_2\cdots\&b_n\)。它满足 \(Y\&X=X\)。
接下来，我们需要确保 \(Y\) 恰好等于 \(X\)。类似地，找到不同的最高位 \(B\)（如果存在）并将其变为 \(0\)。如果修改 \(b_k\) 将 \(B\) 位变为 0。可以证明，最优情况下，只需对单个元素进行一次操作即可同时纠正所有较低的不同位。
当 \(n \ge 2\) 时，可能会出现一个问题：如果我们在某个位上修改 \(b_k\)，而除了 \(b_k\) 之外的所有元素在该位上都是 1，那么 \(Y \neq X\) 会再次出现。为了避免这种情况，通常最优的操作是选择一个不会引起这种冲突的元素。
基于此，我们可以轻松编写 \(O(nq)\) 的代码并提交。
参考代码
Step 2
得到 \(Y\) 后，我们尝试加速该过程。
将 \(X\) 的位按降序表示为 \(x_1,x_2\cdots x_k\)。
我们从高位到低位处理这些位。在第 \(i\) 次处理时，所有包含 \(x_1,x_2\cdots,x_{i-1}\) 但不包含 \(x_i\) 的 \(a_i\) 将被处理。这可以通过卷积加容斥解决。
参考代码
Step 3
为了使 \(Y\) 恰好等于 \(X\)，我们找到 \(X\) 和 \(Y\) 不同的最高位 \(B\)。然后我们寻找一个元素 \(a_k\)，使得修改它所需的操作次数最少，并且不会向 \(Y\) 添加新的位。
令 \(b\) 为第二步中改变的最高位。我们枚举 \([b+1,20]\)。如果在第 \(i\) 位，0 至少出现两次，则找到低 \(i\) 位中值最大的数（即 \(a_k\&(2^i-1)\)）并在 \(O(1)\) 时间内计算。
注意 \(X=Y\) 的特殊情况。
参考代码
Reference
Pinely Round 5 editorial