2798. 斐波那契数列和

鬼知道这题我做了多久，果然还是太菜…发一下题解减少大家的做作业时间 = =||

• 网上看到一个结论：第 $n$ 个斐波那契数有 $(n+1)/2$ 种不相同的斐波那契数拆分。比如题目中的13是第6个斐波那契数，它的拆分有 $(6+1)/2=3$ 种

  那么，假如这个数不拆分，有 1 种情况；假如这个数拆分，有 $(n+1)/2-1=(n-1)/2$ 种情况

斐波那契数列的递推公式为：$\textrm{fib}[i]=\textrm{fib}[i-1]+\textrm{fib}[i-2]$，这说明，数列中的任何一项（除了第一项和第二项）只能分解为前两项的和

我们先用贪心算法，令 $n$ 不断减去小于等于 $n$ 的、最大的斐波那契数，就能得到一个和为 $n$ 的方案，这个方案中没有两个斐波那契数是相邻的。令这个方案表示为 $\textrm{f}={f_1,f_2,…}$, $\textrm{pos}={p_1,p_2,…},$ 其中 $f_i$ 表示斐波那契数，$p_i$ 表示这个数是第 $i$ 个斐波那契数。比如，$16=13+3$，那么 $\textrm{f}={3,13},\textrm{pos}={3,6}$，并且这样的方案有且仅有一种

动态规划：令 $dp[i][0]+dp[i][1]$ 表示 $\textrm{f}$ 中前 $i$ 个元素所有拆分的方案数。$dp[i][0]$ 表示拆分第 $i$ 个元素，$dp[i][1]$ 表示不拆分第 $i$ 个元素

1. 如果第 $i$ 个元素不拆分，$dp[i][1]=dp[i-1][0]+dp[i-1][1]$
2. 如果第 $i$ 个元素拆分，那么它可以拆分成它的前两项的和 $\textrm{f}[i]=\textrm{fib}[p_i-1]+\textrm{fib}[p_i-2]$。如果 $\textrm{fib}[p_i-1],\textrm{fib}[p_i-2]$ 中有一项能继续分解，那么一定是 $\textrm{fib}[p_i-2]$. 可以发现，每拆分一个数，就需要占用可拆分范围内的两个空位
   • 如果第 $i-1$ 个元素不拆分，那么可以用 $(\textrm{pos}[i-1],\textrm{pos[i]})$ 范围内的斐波那契数来拆分
   • 如果第 $i-1$ 个元素拆分，那么可以用 $[\textrm{pos}[i-1],\textrm{pos[i]})$ 范围内的斐波那契数来拆分

$$
dp[i][0]=dp[i-1][1]\times \frac{\textrm{pos}[i]-\textrm{pos[i-1]-1}}{2}+dp[i-1][0]\times \frac{\textrm{pos}[i]-\textrm{pos[i-1]}}{2}
$$

综上所述，状态转移方程为
$$
\begin{cases}dp[i][1]=dp[i-1][0]+dp[i-1][1]\dp[i][0]=dp[i-1][1]\times \frac{\textrm{pos}[i]-\textrm{pos[i-1]-1}}{2}+dp[i-1][0]\times \frac{\textrm{pos}[i]-\textrm{pos[i-1]}}{2}\end{cases}
$$
初始条件：$dp[1][1]=1,dp[1][0]=(\textrm{pos}[1]-1)/2$ (利用了第二行的结论)

做题的时候注意下标

DP+滚动数组：

def dp(l):
    sp, nsp = (l[0] - 1) // 2, 1
    for cur, pre in zip(l[1:], l):
        sp, nsp = (cur - pre) // 2 * sp + (cur - pre - 1) // 2 * nsp, sp + nsp
    return sp + nsp

其中，l为n的最简斐波那契拆分对应的下标
例如n为16时，l为[3, 6]，即16 == fib[3] + fib[6] == 3 + 13
sp和nsp表示split(拆分这个斐波那契数)、not split(不拆分这个斐波那契数)

完整代码：

from bisect import bisect_right as br

fib = [1, 1]
while fib[-1] < 1e18:
    fib.append(fib[-1] + fib[-2])


def split(x):
    while x > 0:
        idx = br(fib, x) - 1
        x -= fib[idx]
        yield idx


def dp(l):
    sp, nsp = (l[0] - 1) // 2, 1
    for cur, pre in zip(l[1:], l):
        sp, nsp = (cur - pre) // 2 * sp + (cur - pre - 1) // 2 * nsp, sp + nsp
    return sp + nsp


for t in range(int(input())):
    print(f'case #{t}:')
    print(dp(list(split(int(input())))[::-1]))