← 返回题目列表

Codeforces · 1718/B

B. 斐波那契字符串

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

在布里亚特的所有学校,$$$1$$$ 班上,每个人都会学习斐波那契弦理论。

“块是字符串的一个子段,其中所有字母都相同,并且左右两侧以字符串的末端或块中字母以外的字母为界。如果将字符串分为块时,如果它们的长度按照它们在字符串中出现的顺序形成斐波那契数列,则该字符串称为斐波那契字符串($$$f_0 = f_1 = 1$$$, $$$f_i = f_{i-2} + f_{i-1}$$$),从该序列的第 0 个成员开始,如果可以重新排序其字母以获得斐波那契字符串,则该字符串称为半斐波那契字符串。”

布伦卡决定进入布里亚特国立大学,但在入学考试时她面临着一项艰巨的任务。给她一个由布里亚特字母表中的字母组成的字符串(其中恰好包含 $$$k$$$ 字母),并询问给定的字符串是否是半斐波那契数列。该字符串可能很长,因此她得到的不是该字符串,而是该字符串中每个字母的出现次数($$$c_i$$$ 表示第 $$$i$$$ 个字母)。不幸的是,布伦卡不再记得斐波那契弦理论,所以如果没有你的帮助,她将无法通过考试。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 测试用例的数量。以下是输入数据集的描述。

每个测试用例的第一行包含一个整数 $$$k$$$ ($$$1 \leq k \leq 100$$$) — 字母表中的字母数。

每个测试用例的第二行包含 $$$k$$$ 整数 $$$c_1, c_2, \ldots, c_k$$$ ($$$1 \leq c_i \leq 10^9$$$) — 字符串中每个字母出现的次数。

输出

对于每个测试用例,如果相应的字符串是半斐波那契,则打印字符串“YES”,如果不是,则打印“NO”。

在任何情况下都可以打印“YES”和“NO”(例如,字符串“yEs”、“yes”、“Yes”将被识别为肯定答案)。

示例

输入 #1

6
1
1
2
1 1
2
1 2
3
3 1 3
2
7 5
6
26 8 3 4 13 34

输出 #1

YES
YES
NO
YES
NO
YES

注意

在第一个测试用例中,单字符字符串是半斐波那契字符串,它本身就是斐波那契字符串。

在第二个测试用例中,两个不同字符的字符串是斐波那契数。

在第三个测试用例中,字符串“abb”(令字母表中的第一个字母为 a,第二个字母为 b)不是半斐波那契字符串,因为其字母的排列(“abb”、“bab”和“bba”)都不是斐波那契字符串。

在第四个测试用例中,字符串“abaccac”的字母的两个排列(第一个字母是a,第二个字母是b,第三个字母是c)是斐波那契字符串——“abaaccc”和“cbccaaa”。