Alice and the Cake

题意翻译

Alice 有一块蛋糕，她可以对其执行恰好 $n-1$ 次操作，每次操作她可以选择当前所有蛋糕中满足其重量 $w\geqslant 2$ 的一块，然后将其切割成质量分别为 $\lfloor\dfrac w2\rfloor$ 和 $\lceil\dfrac w2\rceil$ 的两块。 现在，给定执行完所有操作后 $n$ 块蛋糕的重量 $a_1,a_2\cdots,a_n$，请判断是否存在一个初始蛋糕重量和操作序列使得最终能得到给定的 $n$ 块蛋糕。如果能，输出 `YES`，否则输出 `NO`。 注意，本题输出不区分大小写，即将 `YES` 输出成 `yes`、`Yes`、`yEs` 仍旧会被算作正确答案。 数据范围： - $t$ 组数据，$1\leqslant t\leqslant 10^4$。 - $1\leqslant n,\sum n\leqslant 2\times 10^5$。 - $1\leqslant a_i\leqslant 10^9$。 Translated by Eason_AC

题目描述

Alice has a cake, and she is going to cut it. She will perform the following operation $ n-1 $ times: choose a piece of the cake (initially, the cake is all one piece) with weight $ w\ge 2 $ and cut it into two smaller pieces of weight $ \lfloor\frac{w}{2}\rfloor $ and $ \lceil\frac{w}{2}\rceil $ ( $ \lfloor x \rfloor $ and $ \lceil x \rceil $ denote [floor and ceiling functions](https://en.wikipedia.org/wiki/Floor_and_ceiling_functions), respectively). After cutting the cake in $ n $ pieces, she will line up these $ n $ pieces on a table in an arbitrary order. Let $ a_i $ be the weight of the $ i $ -th piece in the line. You are given the array $ a $ . Determine whether there exists an initial weight and sequence of operations which results in $ a $ .

输入输出格式

输入格式

The first line contains a single integer $ t $ ( $ 1 \le t \le 10^4 $ ) — the number of test cases. The first line of each test case contains a single integer $ n $ ( $ 1 \le n \le 2 \cdot 10^5 $ ). The second line of each test case contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 1 \le a_i \le 10^9 $ ). It is guaranteed that the sum of $ n $ for all test cases does not exceed $ 2 \cdot 10^5 $ .

输出格式

For each test case, print a single line: print YES if the array $ a $ could have resulted from Alice's operations, otherwise print NO. You may print each letter in any case (for example, YES, Yes, yes, yEs will all be recognized as positive answer).

输入输出样例

输入样例 #1

14
1
327
2
869 541
2
985214736 985214737
3
2 3 1
3
2 3 3
6
1 1 1 1 1 1
6
100 100 100 100 100 100
8
100 100 100 100 100 100 100 100
8
2 16 1 8 64 1 4 32
10
1 2 4 7 1 1 1 1 7 2
10
7 1 1 1 3 1 3 3 2 3
10
1 4 4 1 1 1 3 3 3 1
10
2 3 2 2 1 2 2 2 2 2
4
999999999 999999999 999999999 999999999

输出样例 #1

YES
NO
YES
YES
NO
YES
NO
YES
YES
YES
YES
NO
NO
YES

说明

In the first test case, it's possible to get the array $ a $ by performing $ 0 $ operations on a cake with weight $ 327 $ . In the second test case, it's not possible to get the array $ a $ . In the third test case, it's possible to get the array $ a $ by performing $ 1 $ operation on a cake with weight $ 1\,970\,429\,473 $ : - Cut it in half, so that the weights are $ [985\,214\,736, 985\,214\,737] $ . Note that the starting weight can be greater than $ 10^9 $ .In the fourth test case, it's possible to get the array $ a $ by performing $ 2 $ operations on a cake with weight $ 6 $ : - Cut it in half, so that the weights are $ [3,3] $ . - Cut one of the two pieces with weight $ 3 $ , so that the new weights are $ [1, 2, 3] $ which is equivalent to $ [2, 3, 1] $ up to reordering.

题意翻译

Alice 有一块蛋糕，她可以对其执行恰好 $n-1$ 次操作，每次操作她可以选择当前所有蛋糕中满足其重量 $w\geqslant 2$ 的一块，然后将其切割成质量分别为 $\lfloor\dfrac w2\rfloor$ 和 $\lceil\dfrac w2\rceil$ 的两块。 现在，给定执行完所有操作后 $n$ 块蛋糕的重量 $a_1,a_2\cdots,a_n$，请判断是否存在一个初始蛋糕重量和操作序列使得最终能得到给定的 $n$ 块蛋糕。如果能，输出 `YES`，否则输出 `NO`。 注意，本题输出不区分大小写，即将 `YES` 输出成 `yes`、`Yes`、`yEs` 仍旧会被算作正确答案。 数据范围： - $t$ 组数据，$1\leqslant t\leqslant 10^4$。 - $1\leqslant n,\sum n\leqslant 2\times 10^5$。 - $1\leqslant a_i\leqslant 10^9$。 Translated by Eason_AC