题意
现在我们有 $k$ 种字符，第 $i$ 种字符有 $a_i$ 个，现在我们要将这 $\sum^n_{i=1}a_i$ 个字符按照某种顺序排列，使其符合以下形式，就称它是合法的：
1个相同的-1个相同的-2个相同的-3个相同的-5个相同的-8个相同的 $...$
很显然这是个菲波那切数列($1-1-2-3-5-8- ...$ )
例如： $abaabbbcccccaaaaaaaa$ 就是合法的，但是 $ aabbcccddddd $ 就是不合法的。现在给出你每种字符的数量，让你判断是否可以组成合法的串。
思路
很容易看出一个串合法的话，它所有字符的数量肯定是斐波那契数列的前缀和 (1,2,4,7,12)，如果它所有字符的数量都不符合的话，这个串显然是不合法的。
既然一个串的字符数量已经合法了的话，我们就开始考虑如何去分配了。
先看样例的这一组:
2
7 5我们可以判断它的数量是合法的，接下来我们把 5 它和斐波那契数列对照起来看:
7 5
1 1 2 3 5这时候我们有两种选择：
- 先用数量少的字符去放小的空
- 先用数量多的字符去放大的空
如果我们选择第一种的话:数量为 5 的字符会放满 1,1,2 后留下 1,接下来就无法放了。
如果我们选择第二种的话:数量为 7 的字符会放满 5 后留下 2，接下来因为 5 比 2 大所以用 5 放满 2,3 最后用 2 放满 1,1。
可以发现第二种更优。
灵魂拷问：为什么???
因为斐波那契额数列是升序的，小的放小的后只会越来越小，这剩下的字符就只能放在小的空，但是小的空已经被用了很多了，所以就很难处理了；但是第二种方案虽然也会变得更小，但是小的空没有被填满，所以会更加优秀。
__
明白了这个道理后我们就可以有一个贪心的做法了，每次选择 $a$ 与 斐波那契额数组中的最大值进行比较，如果 $a$ 的最大值比斐波那契中最大值的大的话，就讲 $a$ 中的最大值减去斐波那契中的，将斐波那契中的最大值删掉（被填满了）。但如果 $a$ 中的最大值小于斐波那契中的最大值，也就是说这个空没有字符能填，即这个串不合法。
最后在找最大的时候可以用堆优化，具体看代码（有注释）：
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn=110;
ll t,n,a[maxn];
map<ll,ll>mp;//如果mp==true的话就说明所有字符的和为x的串数量合法
struct E{
ll val,id;
bool operator==(const E&x)const{
return id==x.id;
}bool operator<(const E&x)const{
return val<x.val;
}//因为用了STL所以要重载运算符
};
struct Heap{//因为STL的堆不支持删除，所以就加了点料
priority_queue<E>q;
priority_queue<E>d;
void push(E x){q.push(x);}
void del(E x){d.push(x);}
E top(){
while(!q.empty()&&!d.empty()&&q.top()==d.top()){q.pop(),d.pop();}
if(q.empty())return E{-1,-1};
return q.top();
}
void init(){
while(!q.empty())q.pop();
while(!d.empty())d.pop();
return;
}
}heap,fib_heap;
void init(ll M){//初始化
heap.init();fib_heap.init();//堆清空
mp[1]=1;fib_heap.push({1,1});
ll fir=1,sec=1,cnt=1,sum=2;
while(sum<=M){
fib_heap.push({sec,++cnt});
ll tmp=sec;sec+=fir;
fir=tmp;mp[sum]=cnt;
sum+=sec;
}
return;
}
int main(){
init(1e11);
scanf("%lld",&t);
while(t--){
scanf("%lld",&n);
ll sum=0;
for(int i=1;i<=n;i++)scanf("%lld",&a[i]),sum+=a[i];
if(!mp[sum]){printf("NO\n");continue;}//数量不合法
init(sum);
for(int i=1;i<=n;i++)heap.push(E{a[i],i});
int last=0;bool flag=0;
while(1){
E x=heap.top(),y=fib_heap.top(),tmp=E{0,0};
if(x.id==-1&&y.id==-1)break;
if(x.id==last){heap.del(x);tmp=x;x=heap.top();}//不能两次选同一个字符
if(x.val==y.val)heap.del(x),fib_heap.del(y),last=x.id;//相等就相当于都删去
else if(x.val<y.val){flag=1;break;}//不合法
else if(x.val>y.val)fib_heap.del(y),heap.del(x),heap.push(E{x.val-y.val,x.id}),last=x.id;
if(tmp.id>0)heap.push(tmp);
}
if(flag)printf("NO\n");
else printf("YES\n");
}//
return 0;
}