CF1718B Fibonacci Strings

在布里亚特的所有学校里，$1$ 年级的学生都会学习斐波那契字符串的理论。 “一个块是指字符串中的一个子段，其中所有字母都相同，并且该子段的左右边界要么是字符串的两端，要么是与该块字母不同的字母。若将字符串划分为若干块，这些块的长度按照它们在字符串中出现的顺序，依次组成斐波那契数列（$f_0 = f_1 = 1$，$f_i = f_{i-2} + f_{i-1}$），且从该数列的第零项开始，则称该字符串为斐波那契字符串。如果可以重新排列字符串中的字母，使其成为斐波那契字符串，则称该字符串为半斐波那契字符串。” Burenka 决定报考布里亚特国立大学，但在入学考试中她遇到了一个难题。她得到了一个只包含布里亚特字母表（恰好包含 $k$ 个字母）中字母的字符串，要求判断该字符串是否为半斐波那契字符串。由于字符串可能非常长，因此她只得到了每个字母出现的次数（第 $i$ 个字母出现了 $c_i$ 次）。不幸的是，Burenka 已经不记得斐波那契字符串的理论了，如果没有你的帮助，她将无法通过考试。

第一行包含一个整数 $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" 都会被认为是肯定答案）。

在第一个测试用例中，单字符字符串本身就是斐波那契字符串，因此是半斐波那契字符串。 在第二个测试用例中，由两个不同字符组成的字符串是斐波那契字符串。 在第三个测试用例中，字符串 "abb"（假设字母表的第一个字母为 a，第二个字母为 b）不是半斐波那契字符串，因为无论如何排列其字母（"abb"、"bab"、"bba"），都无法成为斐波那契字符串。 在第四个测试用例中，字符串 "abaccac"（第一个字母为 a，第二个为 b，第三个为 c）有两种排列方式可以成为斐波那契字符串——"abaaccc" 和 "cbccaaa"。 由 ChatGPT 4.1 翻译