P4133 {{[BJOI2012] Maximum Number of Ways}}

{{}}

{{The second stage is related to the famous Fibonacci sequence. Every OIer on Earth knows: $$F_n = \begin{cases} 1 & (n \le 2) \\ F_{n-1}+F_{n-2} & (n \ge 3) \end{cases}$$ Each term is called a Fibonacci number. Now given a positive integer $n$, it can be written as a sum of some Fibonacci numbers. If we require that in each representation the Fibonacci numbers are distinct (no repetition), then for a given $n$, how many different ways can it be written?}}

{{A single integer $n$.}}

{{Output a single integer representing the number of ways.}}

{{Hint: 16 = 3 + 13 = 3 + 5 + 8 = 1 + 2 + 13 = 1 + 2 + 5 + 8. Constraints For 30% of the testdata, $n \le 256$. For 100% of the testdata, $n \le 10^{18}$.}} Translated by ChatGPT 5