A16667 | $Binary Wine$

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

给定 $n$ 个整数 $a_1,a_2,\ldots,a_n$，其中 $a_i$ 的范围为 $[0,2^{30})$。 你可以花费 $1$ 个金币将任意 $a_i$ 增加 $1$。你可以进行任意次数的该操作。 现在有 $q$ 个独立的询问，每个询问给出一个整数 $c$，同样满足 $c$ 的范围为 $[0,2^{30})$。你希望存在一个长度为 $n$ 的序列 $b$，满足以下条件： - 对于每个 $1\le i\le n$，$0\le b_i\le a_i$。 - $b_1\oplus b_2\oplus\ldots\oplus b_n=c$，其中 $\oplus$ 表示按位异或运算。 请你计算，为了让存在这样的 $b$，你最少需要花费多少金币（即对 $a$ 进行若干次 $+1$ 操作后有解）。 各个询问相互独立，某一次对 $a$ 所做的操作不会影响其他询问。

第一行输入测试组数 $t$（$1 \le t \le 10^4$）。接下来是 $t$ 组测试数据。 每组测试数据的第一行包含两个整数 $n,q$（$1\le n\le 5\cdot 10^5$，$1\le q\le 5\cdot 10^4$），表示序列长度和询问个数。 第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$（$0\le a_i<2^{30}$），表示初始序列 $a$。 接下来的 $q$ 行，每行一个整数 $c$（$0\le c<2^{30}$），表示目标异或结果。 保证所有测试数据中 $\sum n\le 5\cdot10^5$，$\sum q\le 5\cdot10^4$。

对于每个询问，输出一个整数，表示为使存在合适的 $b$，你最少需要花费的金币数。

输入 #1

4
2 1
5 7
9
3 1
9 9 8
24
6 4
1 1 4 5 1 4
10
20
30
40
1 1
0
0

输出 #1

C++ 编辑器

输入

输出