合并石头__牛客网

$\hspace{15pt}$ 题目来源：https://atcoder.jp/contests/abc390/tasks/abc390_d

有 $N$ 个袋子，编号为 $1,2,\dots,N$ 。第 $i$ 个袋子初始装有 $A_i$ 块石头。允许进行如下操作任意次数（包括 $0$ 次）：选择两个袋子 $X$ 与 $Y$ ，将袋子 $X$ 中的全部石头移入袋子 $Y$ ，使得 $X$ 的石头数变为 $0$ ， $Y$ 的石头数增加相应数量。

$\hspace{15pt}$ 在进行若干次操作后，设第 $i$ 个袋子的最终石头数为 $B_i$ 。请计算不同的 $B_1\oplus B_2\oplus\cdots\oplus B_N$ 的取值个数，其中 $\oplus$ 表示按位 XOR。可以证明，在本题的约束条件下，可能的取值是有限的。

$\hspace{15pt}$ 【名词解释】
$\hspace{23pt}\bullet\,$ 按位 XOR：对非负整数 $a,b$ ，其按位 XOR $a\oplus b$ 的二进制定义为：对所有 $k\geqq 0$ ，在 $a\oplus b$ 的二进制表示的 $2^k$ 位上，当且仅当 $a$ 与 $b$ 的该位中恰有一位为 $1$ 时该位为 $1$ ，否则为 $0$ 。
$\hspace{23pt}\bullet\,$ 示例： $3\oplus 5=6$ （二进制为 $011\oplus 101=110$ ）。

$\hspace{15pt}$ 样例解释：
$\hspace{23pt}\bullet\,$ 若选择袋子 $1$ 与 $3$ 执行一次操作（将袋子 $1$ 的石头移入袋子 $3$ ），则三个袋子的石头数变为 $B_1=0,B_2=5,B_3=9$ ，此时 $B_1\oplus B_2\oplus B_3=0\oplus 5\oplus 9=12$ 。
$\hspace{23pt}\bullet\,$ 在所有可能的操作序列中，异或值的集合为 $\{0,12,14\}$ ，共有 $3$ 个不同取值，故答案为 $3$ 。

$\hspace{15pt}$ 样例解释：
$\hspace{23pt}\bullet\,$ 初始异或为 $A_1\oplus A_2=0$ （因为两数相等）。
$\hspace{23pt}\bullet\,$ 若将其中一个袋子的石头全部移入另一个袋子，则最终为 $[0,2A_1]$ 或 $[2A_1,0]$ ，此时异或为 $2A_1$ 。因此可能的异或值为 $\{0,2A_1\}$ ，数量为 $2$

合并石头

输入描述:

输出描述:

输入

输出

说明

输入

输出

说明

输入

输出

备注:

问题信息

热门推荐

相关试题