Description

第二关和很出名的斐波那契数列有关, 地球上的 OIer 都知道:

\[F_1 = 1, F_2 = 2, F_i = F_{i-1} + F_{i-2}\]

每一项都可以称为斐波那契数. 现在给一个正整数 \(n\), 它可以写成一些斐波那契数的和的形式. 如果我们要求不同的方案中不能有相同的斐波那契数, 那么对一个 \(n\) 最多可以写出 多少种方案呢?

Input

只有一个整数 \(n\).

Output

一个整数, 代表方案数.

Sample Input

16

Sample Output

4

Data Range

对于 30% 的数据,\(n \leq 256\)

对于 100% 的数据,\(n \leq 10^{18}\)

Explanation

看这道题的位置 (第二题) 应该可以猜出是一道 DP 题~

但是怎么 DP 呢? 我们会发现斐波那契数列有这样一个性质: 某一项的数等于其前面两项 的数的和 (这不是废话吗). 但是在这里我们会发现, 只要选择了一个斐波那契数, 那么 它就可以拆成两个数的和, 进一步扩展方案数.

进一步地, 我们会发现其实斐波那契数很少, 在 \(2^{64}\) 的范围内不会超过 \(64\) 个 (具体地, 大约只有 \(50\) 个左右就会开始溢出).

所以就是一个常数很小的 \(O(\log(2^{64}) \cdot \log\log(2^{64}))\) 复杂度的动规了~

但是一开始并没有想出来 QwQ

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <algorithm>

using namespace std;
typedef long long lli;
const int maxn = 110;

lli n, fib[maxn], comp[maxn];
lli dp[maxn][2];

int main(int argc, char** argv)
{
    scanf("%lld", &n);
    // Generating fibonacci numbers
    fib[1] = 1, fib[2] = 2;
    for (fib[0] = 2; fib[fib[0]] < n; )
        fib[++fib[0]] = fib[fib[0] - 1] + fib[fib[0] - 2];
    // Generating compensate numbers for fib[] array.
    for (int i = fib[0]; i >= 1; i--)
        if (n >= fib[i])
            n -= fib[i], comp[++comp[0]] = i;
    sort(comp + 1, comp + comp[0] + 1);
    // Dynamic programming.
    dp[1][true] = 1;
    dp[1][false] = (comp[1] - 1) / 2;
    for (int i = 2; i <= comp[0]; i++) {
        dp[i][true] = dp[i-1][true] + dp[i-1][false];
        dp[i][false] = dp[i-1][true] * ((comp[i] - comp[i-1] - 1) / 2)
            + dp[i-1][false] * ((comp[i] - comp[i-1]) / 2);
    }
    // Finalize results
    lli res = dp[comp[0]][true] + dp[comp[0]][false];
    printf("%lld\n", res);
    return 0;
}