990 . 費氏數拆分
TopCoder
Tags
Description
莫妮卡熱愛數字，她非常喜歡有特殊性質的數字，例如完全數、費氏數等等。她認為一個正整數越像是費氏數列中的數字就越美麗，因此她定義一個正整數 $n$ 的壞度為最小的 $k$ 滿足存在 $k$ 個出現在費氏數列中的數且它們的總和為 $n$，壞度越低就代表這個數字越美。舉例來說，$5$ 的壞度為 $1$，因為 $5$ 出現在費氏數列中；$26$ 的壞度為 $2$，因為 $26 = 13 + 13$。
現在莫妮卡有兩個正整數 $x, m$，她想要知道 $x + 1, x + 2, \ldots, x + m$ 的壞度分別是多少，但因為她正沉迷於其他計算工作裡無法抽身，請你幫幫她計算出這些壞度。
需要注意的是正整數 $x$ 非常大！為了方便，假設 $x$ 的壞度為 $n$，那莫妮卡會告訴你一個序列 $a_1, a_2, \ldots, a_n$，滿足
$$
x = \sum_{i = 1}^ {n}F_{a_i}
$$
費氏數列 $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}
$$
Input Format
輸入第一行有兩個正整數 $n, m$。
第二行有 $n$ 個正整數 $a_1, a_2, \ldots, a_n$。
- $1 \leq n, m \leq 5 \times 10^ 5$
- $1 \leq a_i \leq 10^ 6$
- 令 $x = \sum_{i = 1}^ {n}F_{a_i}$，保證 $x$ 的壞度為 $n$。也就是說，不存在 $n - 1$ 個費氏數加起來為 $x$。
Output Format
輸出一行，該行包含 $m$ 個正整數，其中第 $i$ 個數為 $x + i$ 的壞度。
Sample Input 1
2 5 4 1
Sample Output 1
1 2 2 1 2
Sample Input 2
3 9 7 5 7
Sample Output 2
3 4 1 2 2 2 3 2 3
Sample Input 3
1 10 1000000
Sample Output 3
2 2 2 3 2 3 3 2 3 3
Hints
費氏數列前幾項：$F = [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, \ldots]$。
在第一筆範例測資中，$x = F_4 + F_1 = 4$。
在第二筆範例測資中，$x = F_7 + F_5 + F_7 = 31$。
這首歌可能會有用。
Problem Source
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~2 | 範例測資。 | 0 |
| 2 | 3~27 | $a_i \leq 60$ | 30 |
| 3 | 28~52 | 所有 $a_i$ 皆相異。 | 50 |
| 4 | 0~72 | 無特別限制。 | 20 |