← 返回题目列表

Codeforces · 1868/B2

B2. 糖果派对(硬版)

中文机器翻译题面 查看原题

这是问题的困难版本。唯一的区别是,在这个版本中,每个人只能向不超过一个人提供糖果,并且从不超过一个人那里接收糖果。请注意,一次提交不能同时通过两个版本的问题。只有当问题的两个版本都得到解决时,你才能进行黑客攻击。

中考结束后,大牛和他的朋友们要去聚会。每个人都会带着一些糖果来。

聚会上将会有 $$$n$$$ 人。最初,第 $$$i$$$ 人有 $$$a_i$$$ 糖果。聚会期间,他们会交换糖果。为此,他们将以任意顺序排队,并且每个人最多执行一次以下操作:

- 选择一个整数 $$$p$$$ ($$$1 \le p \le n$$$) 和一个非负整数 $$$x$$$,然后把他的 $$$2^{x}$$$ 糖果给第 $$$p$$$ 人。请注意,一个人不能给予比他目前拥有的更多的糖果(他可能以前从别人那里收到过糖果),并且他不能给自己糖果。

丹尼尔喜欢公平,所以当且仅当每个人都收到不超过一个人的糖果时,他才会感到高兴。与此同时,他的朋友汤姆喜欢平均,所以当且仅当所有的人在所有交换后都拥有相同数量的糖果时,他才会感到高兴。

确定是否存在交换糖果的方法,以便丹尼尔和汤姆在交换后都会开心。

输入

输入的第一行包含一个整数 $$$t$$$ ($$$1\le t\le 1000$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2\le n\le 2\cdot 10^5$$$) — 聚会的人数。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1,a_2,\ldots,a_n$$$ ($$$1\le a_i\le 10^9$$$) — 每个人拥有的糖果数量。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2\cdot 10^5$$$。

输出

对于每个测试用例,如果存在交换糖果以使 Daniel 和 Tom 都开心的方法,则打印“Yes”(不带引号),否则打印“No”(不带引号)。

您可以在任何情况下输出答案(大写或小写)。例如,字符串“yEs”、“yes”、“Yes”和“YES”将被识别为肯定响应。

示例

输入 #1

6
3
2 4 3
5
1 2 3 4 5
6
1 4 7 1 5 4
2
20092043 20092043
12
9 9 8 2 4 4 3 5 1 1 1 1
6
2 12 7 16 11 12

输出 #1

Yes
Yes
No
Yes
No
Yes

注意

在第一个测试用例中,第二个人给第一个人$$$1$$$糖果,那么所有人都有$$$3$$$糖果。

在第二个测试用例中,第四个人给第二个人$$$1$$$糖果,第五个人给第一个人$$$2$$$糖果,第三个人什么也不做。交换后,每个人都有 $$$3$$$ 糖果。

在第三个测试用例中,不可能所有人都拥有相同数量的糖果。

在第四个测试用例中,两个人不需要做任何事情。