309682: CF1718B. Fibonacci Strings
Memory Limit：256 MB
Time Limit：2 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
Fibonacci Strings
题意翻译
给你一个数列 $\{c_k\}$。 你可以执行若干轮操作（轮数由你决定）。对于第 $i$ 轮操作： - 选定一个 $[1,k]$ 范围内的整数 $d_i$。当 $i \ge 2$ 时，必须保证 $d_i \neq d_{i-1}$。 - 将 $c_{d_i}$ 减去 $f_i$，其中 $f_i$ 是斐波那契数列（$1,1,2,3,5,8,13,\ldots$）的第 $i$ 项。 问：你能否让 $c_1$ 至 $c_k$ 全为 $0$？ ------------ **本题有多组数据（$t$ 组）。** 对于 $100\%$ 的数据，$1 \le k \le 100$，$1 \le t \le 10^4$（即 $1 \le \sum k \le 10^6$），$1 \le c_i \le 10^9$（即每组数据中 $1 \le \sum _{i=1}^n c_i \le 10^{11}$）。题目描述
In all schools in Buryatia, in the $ 1 $ class, everyone is told the theory of Fibonacci strings. "A block is a subsegment of a string where all the letters are the same and are bounded on the left and right by the ends of the string or by letters other than the letters in the block. A string is called a Fibonacci string if, when it is divided into blocks, their lengths in the order they appear in the string form the Fibonacci sequence ( $ f_0 = f_1 = 1 $ , $ f_i = f_{i-2} + f_{i-1} $ ), starting from the zeroth member of this sequence. A string is called semi-Fibonacci if it possible to reorder its letters to get a Fibonacci string." Burenka decided to enter the Buryat State University, but at the entrance exam she was given a difficult task. She was given a string consisting of the letters of the Buryat alphabet (which contains exactly $ k $ letters), and was asked if the given string is semi-Fibonacci. The string can be very long, so instead of the string, she was given the number of appearances of each letter ( $ c_i $ for the $ i $ -th letter) in that string. Unfortunately, Burenka no longer remembers the theory of Fibonacci strings, so without your help she will not pass the exam.输入输出格式
输入格式
The first line contains one integer $ t $ ( $ 1 \leq t \leq 10^4 $ ) — the number of test cases. The following is a description of the input data sets. The first line of each test case contains one integer $ k $ ( $ 1 \leq k \leq 100 $ ) — the number of letters in the alphabet. The second line of each test case contains $ k $ integers $ c_1, c_2, \ldots, c_k $ ( $ 1 \leq c_i \leq 10^9 $ ) — the number of occurrences of each letter in the string.
输出格式
For each test case print the string "YES" if the corresponding string is semi-Fibonacci, and "NO" if it is not. You can print "YES" and "NO" in any case (for example, the strings "yEs", "yes", "Yes" will be recognized as a positive answer).
输入输出样例
输入样例 #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说明
In the first test case, a one-character string is semi-Fibonacci, being itself a Fibonacci string. In the second test case, a string of two different characters is Fibonacci. In the third test case, the string "abb" (let the first of the alphabet letter be a, the second letter b) is not a semi-Fibonacci string, since no permutation of its letters ("abb", "bab", and "bba") is a Fibonacci string. In the fourth test case, two permutations of the letters of the string "abaccac" (the first letter is a, the second letter is b, the third letter is c) are Fibonacci strings — "abaaccc" and "cbccaaa".Input
题意翻译
给你一个数列 $\{c_k\}$。 你可以执行若干轮操作（轮数由你决定）。对于第 $i$ 轮操作： - 选定一个 $[1,k]$ 范围内的整数 $d_i$。当 $i \ge 2$ 时，必须保证 $d_i \neq d_{i-1}$。 - 将 $c_{d_i}$ 减去 $f_i$，其中 $f_i$ 是斐波那契数列（$1,1,2,3,5,8,13,\ldots$）的第 $i$ 项。 问：你能否让 $c_1$ 至 $c_k$ 全为 $0$？ ------------ **本题有多组数据（$t$ 组）。** 对于 $100\%$ 的数据，$1 \le k \le 100$，$1 \le t \le 10^4$（即 $1 \le \sum k \le 10^6$），$1 \le c_i \le 10^9$（即每组数据中 $1 \le \sum _{i=1}^n c_i \le 10^{11}$）。Output
**斐波那契字符串**
**题意翻译**
给你一个数列 $\{c_k\}$。
你可以执行若干轮操作（轮数由你决定）。对于第 $i$ 轮操作：
- 选定一个 $[1,k]$ 范围内的整数 $d_i$。当 $i \ge 2$ 时，必须保证 $d_i \neq d_{i-1}$。
- 将 $c_{d_i}$ 减去 $f_i$，其中 $f_i$ 是斐波那契数列（$1,1,2,3,5,8,13,\ldots$）的第 $i$ 项。
问：你能否让 $c_1$ 至 $c_k$ 全为 $0$？
------------
**本题有多组数据（$t$ 组）。**
对于 $100\%$ 的数据，$1 \le k \le 100$，$1 \le t \le 10^4$（即 $1 \le \sum k \le 10^6$），$1 \le c_i \le 10^9$（即每组数据中 $1 \le \sum _{i=1}^n c_i \le 10^{11}$）。
**题目描述**
在布里亚特的所有学校里，一年级的学生都会学习斐波那契字符串的理论。
“一个块是一个子串，其中所有字母都相同，并且由字符串的末端或除块中字母之外的其他字母在左右两边限定。如果一个字符串在划分为块时，它们的长度按照在字符串中出现的顺序形成斐波那契序列（$ f_0 = f_1 = 1 $，$ f_i = f_{i-2} + f_{i-1} $），从该序列的零项开始，那么这个字符串被称为斐波那契字符串。如果一个字符串可以通过重新排列其字母来得到一个斐波那契字符串，那么它被称为半斐波那契字符串。”
布伦卡决定进入布里亚特国立大学，但在入学考试时，她遇到了一个难题。她得到了一个由布里亚特字母（恰好有 $ 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”。**斐波那契字符串** **题意翻译** 给你一个数列 $\{c_k\}$。 你可以执行若干轮操作（轮数由你决定）。对于第 $i$ 轮操作： - 选定一个 $[1,k]$ 范围内的整数 $d_i$。当 $i \ge 2$ 时，必须保证 $d_i \neq d_{i-1}$。 - 将 $c_{d_i}$ 减去 $f_i$，其中 $f_i$ 是斐波那契数列（$1,1,2,3,5,8,13,\ldots$）的第 $i$ 项。 问：你能否让 $c_1$ 至 $c_k$ 全为 $0$？ ------------ **本题有多组数据（$t$ 组）。** 对于 $100\%$ 的数据，$1 \le k \le 100$，$1 \le t \le 10^4$（即 $1 \le \sum k \le 10^6$），$1 \le c_i \le 10^9$（即每组数据中 $1 \le \sum _{i=1}^n c_i \le 10^{11}$）。 **题目描述** 在布里亚特的所有学校里，一年级的学生都会学习斐波那契字符串的理论。 “一个块是一个子串，其中所有字母都相同，并且由字符串的末端或除块中字母之外的其他字母在左右两边限定。如果一个字符串在划分为块时，它们的长度按照在字符串中出现的顺序形成斐波那契序列（$ f_0 = f_1 = 1 $，$ f_i = f_{i-2} + f_{i-1} $），从该序列的零项开始，那么这个字符串被称为斐波那契字符串。如果一个字符串可以通过重新排列其字母来得到一个斐波那契字符串，那么它被称为半斐波那契字符串。” 布伦卡决定进入布里亚特国立大学，但在入学考试时，她遇到了一个难题。她得到了一个由布里亚特字母（恰好有 $ 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”。
**题意翻译**
给你一个数列 $\{c_k\}$。
你可以执行若干轮操作（轮数由你决定）。对于第 $i$ 轮操作：
- 选定一个 $[1,k]$ 范围内的整数 $d_i$。当 $i \ge 2$ 时，必须保证 $d_i \neq d_{i-1}$。
- 将 $c_{d_i}$ 减去 $f_i$，其中 $f_i$ 是斐波那契数列（$1,1,2,3,5,8,13,\ldots$）的第 $i$ 项。
问：你能否让 $c_1$ 至 $c_k$ 全为 $0$？
------------
**本题有多组数据（$t$ 组）。**
对于 $100\%$ 的数据，$1 \le k \le 100$，$1 \le t \le 10^4$（即 $1 \le \sum k \le 10^6$），$1 \le c_i \le 10^9$（即每组数据中 $1 \le \sum _{i=1}^n c_i \le 10^{11}$）。
**题目描述**
在布里亚特的所有学校里，一年级的学生都会学习斐波那契字符串的理论。
“一个块是一个子串，其中所有字母都相同，并且由字符串的末端或除块中字母之外的其他字母在左右两边限定。如果一个字符串在划分为块时，它们的长度按照在字符串中出现的顺序形成斐波那契序列（$ f_0 = f_1 = 1 $，$ f_i = f_{i-2} + f_{i-1} $），从该序列的零项开始，那么这个字符串被称为斐波那契字符串。如果一个字符串可以通过重新排列其字母来得到一个斐波那契字符串，那么它被称为半斐波那契字符串。”
布伦卡决定进入布里亚特国立大学，但在入学考试时，她遇到了一个难题。她得到了一个由布里亚特字母（恰好有 $ 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”。**斐波那契字符串** **题意翻译** 给你一个数列 $\{c_k\}$。 你可以执行若干轮操作（轮数由你决定）。对于第 $i$ 轮操作： - 选定一个 $[1,k]$ 范围内的整数 $d_i$。当 $i \ge 2$ 时，必须保证 $d_i \neq d_{i-1}$。 - 将 $c_{d_i}$ 减去 $f_i$，其中 $f_i$ 是斐波那契数列（$1,1,2,3,5,8,13,\ldots$）的第 $i$ 项。 问：你能否让 $c_1$ 至 $c_k$ 全为 $0$？ ------------ **本题有多组数据（$t$ 组）。** 对于 $100\%$ 的数据，$1 \le k \le 100$，$1 \le t \le 10^4$（即 $1 \le \sum k \le 10^6$），$1 \le c_i \le 10^9$（即每组数据中 $1 \le \sum _{i=1}^n c_i \le 10^{11}$）。 **题目描述** 在布里亚特的所有学校里，一年级的学生都会学习斐波那契字符串的理论。 “一个块是一个子串，其中所有字母都相同，并且由字符串的末端或除块中字母之外的其他字母在左右两边限定。如果一个字符串在划分为块时，它们的长度按照在字符串中出现的顺序形成斐波那契序列（$ f_0 = f_1 = 1 $，$ f_i = f_{i-2} + f_{i-1} $），从该序列的零项开始，那么这个字符串被称为斐波那契字符串。如果一个字符串可以通过重新排列其字母来得到一个斐波那契字符串，那么它被称为半斐波那契字符串。” 布伦卡决定进入布里亚特国立大学，但在入学考试时，她遇到了一个难题。她得到了一个由布里亚特字母（恰好有 $ 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”。