1454 . 費氏數分解
TopCoder
Tags
Description
莫妮卡熱愛數字，她非常喜歡有特殊性質的數字，例如完全數、費氏數等等。費氏數列 $F_0, F_1, F_2, \ldots$ 為符合以下條件的數列：
$$
F_n =
\begin{cases}
0 & \text{if } n = 0 \\
1 & \text{if } n = 1 \\
F_{n-1} + F_{n-2} & \text{otherwise.}
\end{cases}
$$
這天，一個正在研究費氏數列的數學家向她提出了一個問題：
- 給定 $n, l, r$，是否存在 $n$ 個介於 $l$ 到 $r$ 之間的正整數 $a_1, a_2, \ldots, a_n$，滿足 $\sum_{i = 1}^ {n} F_{a_i}$ 出現在費氏數列中。
聰明的莫妮卡當然馬上就想到如何解決這個問題，但她因為要與人講話太緊張而昏倒了，你能幫幫她回答這個問題嗎？
Input Format
輸入第一行有一個正整數 $t$，代表測資數量。
接下來 $t$ 行，每行有三個正整數 $n, l, r$，代表第 $i$ 筆測資的參數。
- $1 \leq t \leq 10^ 4$
- $1 \leq n \leq 10^ 9$
- $2 \leq l \leq r \leq 44$
注意到 $F_{44} = 701408733 < 10^ 9$。
Output Format
對於每筆測資，若該筆測資不存在 $n$ 個符合條件的正整數，則輸出一行 No。否則先在第一行輸出 Yes，第二行輸出 $r - l + 1$ 個整數 $c_l, c_{l + 1}, \ldots, c_r$，代表序列 $a$ 裡面出現了 $c_i$ 次 $i$。
你的答案會被視為正確若滿足以下所有條件：
- $\sum_{i = l}^ {r} c_i = n$
- $\sum_{i = l}^ {r} F_ic_i$ 出現在費氏數列中。
Sample Input 1
7 1 2 2 7 2 3 3 3 6 6 4 5 4 3 3 2 42 44 1201 10 14
Sample Output 1
Yes 1 Yes 6 1 Yes 1 1 0 1 No Yes 4 Yes 0 1 1 Yes 328 236 223 214 200
Hints
在第三筆範例測資中，當 $a = [2, 3, 5]$ 時符合條件，因為 $F_{2} + F_{3} + F_{5} = 1 + 2 + 5 = 8 = F_{6}$。
Problem Source
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0 | 範例測資。 | 0 |
| 2 | 1~10 | $l = 2$ | 20 |
| 3 | 11~20 | $r - l \geq 2$ | 50 |
| 4 | 0~25 | 無特別限制。 | 30 |