题解 - Codeforces Round 1108 (Div. 2)

A

既然给定的 $n$ 是偶数，那么往奇偶性的角度去考虑。

既然第 $i$ 个数从 $S_i=\{-ip_i,0,ip_i\}$ 中选，那么只要我们让这三个数恒为偶数，最终就不可能凑出一个 $1$ 。

那么只需要让 $p_1,p_3,\dots, p_{n-1}$ 为偶数， $p_2,p_4,\dots,p_n$ 为奇数即可。

复杂度 $O(n)$ 。

B

注意到 $n\le 50$ 并且要求 $1\le a_i\le 10^{17}$ ，猜测和 $2^n$ 有关系。

由于 $\sum_{i=1}^{k} 2^{i-1}=2^k -1$ ，那么我们需要一个不是 $2$ 的幂的数字凑出这个 $1$ 。

考虑用较小的数 $3$ ，那么既然要让最终的和能被 $3$ 整除，就让和为 $3\times 2^k$ 。

观察到 $3(\sum_{i=1}^k 2^{i-1})=3\times 2^{k}-3$ ，展开前面的和式为 $3+6+12+24+\cdots$ ，前面只需要再给一个 $1,2$ 就能让最终的和为 $3\times 2^k$ 了。

这里注意 $n=2$ 时，由于 $a_1\mid (a_1+a_2),a_2\mid (a_1+a_2)$ ，可以推出 $a_1\mid a_2$ 且 $a_2\mid a_1$ ，那么就有 $a_1=a_2$ ，这不符合题目要求，于是无解。

综上所述，构造方案如下：

若 $n=1$ ，输出任意数字即可；
若 $n=2$ ，输出 $-1$ ；
否则，输出 $1,2,3\times 2^0,3\times 2^1,\dots, 3\times 2^{n-3}$ 即可。

复杂度 $O(n)$ 。

C

将符合要求的交替数列分为长度为奇数和偶数两类。

先看偶数长度。由于 $a_{i_1}\le a_{i_2},a_{i_3}\le a_{i_4}$ ，那么 $(a_{i_1}-a_{i_2})+(a_{i_3}-a_{i_4})+\cdots \le 0$ ，要让最终的和为 $0$ ，当且仅当 $a_{i_1}=a_{i_2},a_{i_3}=a_{i_4}$ ，以此类推。

按照乘法原理，我们需要在每一个连续的相等段中，选出偶数个数字。也就是说，如果一个相等段长度为 $l$ ，那么在这个段中的选的方案数就是：

$\binom{l}{0}+\binom{l}{2}+\dots+\binom{l}{2\lfloor l/2\rfloor}=2^{l-1}$

其中 $2^{l-1}$ 是根据二项式定理得出的：对 $(1+x)^l$ 二项式展开，分别令 $x=1$ 和 $x=-1$ 即可算出这个数。

再看奇数长度。由于 $a_{i_2}\le a_{i_3},a_{i_4}\le a_{i_5}$ ，那么 $(-a_{i_2}+a_{i_3})+(-a_{i_4}+a_{i_5})+\cdots \ge 0$ 。

又因为 $a_{i_1}\neq 0$ ，所以必须有 $(-a_{i_2}+a_{i_3})+(-a_{i_4}+a_{i_5})+\cdots \ge 1$ ；又因为最终的和为 $0$ ，所以只能是后面这一串等于 $1$ ，并且 $a_{i_1}=-1$ 。

我在赛时对着最后一项看了半天，发现并没有什么特殊的性质，因为按照相同的分析，只能看出 $a_{i_k}>0$ ，但是这个题目只说了负数只有 $-1$ ，所以应当从对称的角度考虑。

也就是说，我们需要让后面的这些 pair 中恰好有一个 pair 的值为 $1$ ，其余的都为 $0$ ，

又因为这个数组是升序排序的，那么这个 $1$ 一定来源于两个相邻的连续段。

考虑按不同的相邻连续段划分所有的方案，那么每一种相邻连续段给出的贡献是：需要在前面 $l_1$ 个数中选奇数个，在 $l_2$ 个数中选奇数个， $-1$ 的段选奇数个，其余段都选偶数个。

由于二项式定理，若干个数选奇数个的方案数等于选偶数个的方案数。

假设有 $c$ 这样的相邻连续段，把偶数长度的答案乘 $c$ 就是奇数的答案。

注意特判没有 $-1$ 的情况。

可以预处理出 $2$ 的幂，复杂度 $O(n)$ 。

D

如果没有一开始的增加操作，推导一下 $a_1\sim a_n$ 的答案是多少。

假设 $2^k$ 是满足 $2^k\mid a_i$ 的最大值，也就是说，所有的 $a_i$ 都在二进制表示的末尾有 $k$ 个 $0$ ，那么一开始就会有 $k$ 步就是把这些 $0$ 除掉。

考虑后续操作，因为每一个数总是被若干次 $-1$ 和若干次 $\div 2$ 变为 $0$ 的，如果只考虑一个数 $x$ 被操作的次数，那么会是 $l(x)+p(x)-1$ 次操作，其中 $l$ 表示二进制表示的长度， $p$ 表示二进制表示中 $1$ 的数量。

那么这个上界是否总能被达到？进行了 $k$ 次操作后，这个数列中一定存在一个奇数，Bob 只需要把这个奇数一直放到第二个位置即可，所以最终的操作次数就是 $k+\sum_{i=1}^n [l(a_i)+p(a_i)-1 - k]=-(n-1)k+\sum_{i=1}^n [l(a_i)+p(a_i)-1]$ 。

接下来我们考虑一开始的增加操作，考虑到上面的分析都和 $\text{lowbit}$ 绕不开，所以这里猜测一个数只能加自己的 $\text{lowbit}$ 的整数倍。

如何证明？假设 $\operatorname{lowbit}(a_i)=L$ ，那么加一个数 $x$ 一定不优于 $x-x\bmod L$ 的代价：从 $k$ 和 $l(a_i),p(a_i)$ 的分析可以轻松得出这一点。

由于这个 $k$ 比较难以处理，所以我们不妨直接枚举 $k=0\sim \log A$ ，然后先把每个 $a_i$ 加到 $2^k\mid a_i$ ，然后考虑最小化 $l(a_i)+p(a_i)$ ，此时每一个 $a_i$ 就是独立的了。

定义 $f(x)=\arg \min_{y\ge x} l(y)+p(y)$ ，根据上面的分析，存在性质 $f(x)=x+p\operatorname{lowbit}(x),p\ge 0$ 。

根据定义和性质，我们可以得出 $f(x)=x$ 或者 $f(x)=f(x+\operatorname{lowbit}(x))$ 。

说人话就是，只能在 $x$ 不断加自己的 $\operatorname{lowbit}$ 的过程中取到。

考虑到当 $x$ 为 $2$ 的幂时，再加 $\operatorname{lowbit}(x)$ 就不会让 $l(x)+p(x)$ 减小了，所以这个过程会持续 $O(\log A)$ 次。

复杂度 $O(n\log^2A)$ 。

E

我以为我能做出这道交互，直接跳过了 D，实际上做了一个小时也没有做出来，掉大分。

首先给出任意一个既有 $0$ 又有 $1$ 的 $x$ ，返回的 $o$ 有三种情况：

$o=x$ ；
$o\subsetneq x$ ；
$x\subsetneq o$ ；

对于情况 $2$ ，可以判断出 $\text{ty} = \&$ ，于是 $x$ 为 $1$ 的所有位上的 $v$ 是已知的，只需要让 $m_0,m_1$ 在这些位上有差异即可，对于情况 $3$ 同理。

所以只需要考虑情况 $1$ ，此时我们无法确定 $\text{ty}$ ，只能考虑 $v$ 是否有特殊位置的值是已知的。

这里只能给出题解的做法了：让询问的 $x=1$ ，我们考虑 $v$ 的最低位，如果 $v$ 的最低位为 $0$ ，说明 $\text{ty}=|$ ，那么 $v=0$ ；反过来看，如果 $v\neq 0$ ，就有 $v$ 的最低位为 $1$ 。

那么我们可以先判断 $v$ 是否为 $0$ ：如果 $v=0$ ，那么返回的 $m_b\oplus v=m_b$ ；反之，如果返回的 $m_b\oplus v=m_0$ 或者 $m_b\oplus v=m_1$ ，那么 $v=0$ 或者 $v=m_0\oplus m_1$ 。

考虑随机化，令 $m_0=0$ ， $m_1=1\oplus 2\operatorname{randint}(0,2^{29}-1)$ ，这里主要是保证 $m_0$ 和 $m_1$ 的最低位不同；此时 $v=m_0\oplus m_1\neq 0$ 的概率是 $2^{-29}$ ，足够低。

在 $T\le 10^5$ 组测试数据的情况下，全部正确的概率为 $(1-2^{-29})^T\approx 1-2^{-29}T\ge 0.9998$ 。

所以通过一步随机化我们可以判出 $v$ 是否为 $0$ ，如果不是 $0$ 只需要看它的最低位即可。

复杂度 $O(1)$ 。