codeforce 1478C C. Nezzar and Symmetric Array 模拟 认真写 C

codeforce 1478C C. Nezzar and Symmetric Array 模拟 认真写 C

https://codeforces.com/contest/1478/problem/C

C. Nezzar and Symmetric Array time limit per test 2 seconds memory limit per test 512 megabytes input standard input output standard output

Long time ago there was a symmetric array a1,a2,…,a2n">a1,a2,…,a2na1,a2,…,a2n consisting of 2n">2n2n distinct integers. Array a1,a2,…,a2n">a1,a2,…,a2na1,a2,…,a2n is called symmetric if for each integer 1≤i≤2n">1≤i≤2n1≤i≤2n, there exists an integer 1≤j≤2n">1≤j≤2n1≤j≤2n such that ai=−aj">ai=?ajai=?aj.

For each integer 1≤i≤2n">1≤i≤2n1≤i≤2n, Nezzar wrote down an integer di">didi equal to the sum of absolute differences from ai">aiai to all integers in a">aa, i. e. di=∑j=12n|ai−aj|">di=∑2nj=1|ai?aj|di=∑j=12n|ai?aj|.

Now a million years has passed and Nezzar can barely remember the array d">dd and totally forget a">aa. Nezzar wonders if there exists any symmetric array a">aa consisting of 2n">2n2n distinct integers that generates the array d">dd.

Input

The first line contains a single integer t">tt (1≤t≤105">1≤t≤1051≤t≤105) — the number of test cases.

The first line of each test case contains a single integer n">nn (1≤n≤105">1≤n≤1051≤n≤105).

The second line of each test case contains 2n">2n2n integers d1,d2,…,d2n">d1,d2,…,d2nd1,d2,…,d2n (0≤di≤1012">0≤di≤10120≤di≤1012).

It is guaranteed that the sum of n">nn over all test cases does not exceed 105">105105.

Output

For each test case, print "YES" in a single line if there exists a possible array a">aa. Otherwise, print "NO".

You can print letters in any case (upper or lower).

Example input Copy

6
2
8 12 8 12
2
7 7 9 11
2
7 11 7 11
1
1 1
4
40 56 48 40 80 56 80 48
6
240 154 210 162 174 154 186 240 174 186 162 210

output Copy

YES
NO
NO
NO
NO
YES

Note

In the first test case, a=[1,−3,−1,3]">a=[1,?3,?1,3]a=[1,?3,?1,3] is one possible symmetric array that generates the array d=[8,12,8,12]">d=[8,12,8,12]d=[8,12,8,12].

In the second test case, it can be shown that there is no symmetric array consisting of distinct integers that can generate array d">dd.

 分析

按照题目说的

很容易发现

顺序没有用，对应的数一定有对应的结果

写的时候一定认真写

比赛的时候写的乱七八糟的，结果用了很久才写出来

写错了好多好多次

按照从小到大排序a数组

那么d数组最后的面的就是n*2*a_0

往前依次有规律递减两个数，d数组倒数第二个是(n-1)*2*a_1*2*a_0

照样子写出来就可以了

代码

#include 
#include 
#include 
#include 
#include 
#include <string.h>
#include 
#include 
#include <string>
#include 
#include 
#include 
#include 
#include 
#include 

https://codeforces.com/contest/1478/submission/105764657