「BJOI 2012」最多的方案

题目大意：给定一个正整数 $n$，求 $n$ 可以表示成多少种斐波那契数的和。$n \leq 10^{18}$

打个表可以发现，最后一个小于等于 $10^{18}$ 的数是 $f[86]$。

先把这个数分解成尽量靠右的 $fibonacci$ 数的和，因为 $f[i]=f[i-1]+f[i-2]$，所以如果把选那些 $fibonacci$ 数压成 $01$ 串的话，$001$ 和 $110$ 的和是一样的。

我们考虑一个 $10000001$ 的串，它的和也是 $10000110,10011010,11101010$ 的和，我们会发现多出来的这三种情况正好是这个 $1$ 和上个 $1$ 之间长度的一半。

设 $dp[i][0/1]$ 表示第 $i$ 个贪心出来的 $fibonacci$ 数的下标选或者不选，那么

$$dp[i][1]=dp[i-1][0]+dp[i-1][1]\\ dp[i][0]=(g[i]-g[i-1])/2*dp[i-1][0]+(g[i]-g[i-1]-1)/2*dp[i-1][1]$$

最后答案就是 $dp[\ ][0]+dp[\ ][1]$

#include <cstdio>
 
typedef long long LL;
LL f[100] = {0, 1, 2}, g[100], dp[100][2], ans, n, m;
 
int main() {
    scanf("%lld", &n);
    for (int i = 3; i <= 86; ++i)
        f[i] = f[i-1] + f[i-2];
    for (int i = 86; i; --i)
        if (n >= f[i]) g[++m] = i, n -= f[i];
    dp[m+1][1] = 1;
    for (int i = m; i; --i) {
        dp[i][1] = dp[i+1][0] + dp[i+1][1];
        dp[i][0] = (g[i] - g[i+1] >> 1) * dp[i+1][0] + (g[i] - g[i+1] - 1 >> 1) * dp[i+1][1];
    }
    printf("%lld\n", dp[1][0] + dp[1][1]);
    return 0;
}