自动搬运

查看原文

来自洛谷，原作者为

	NaCly_Fish 北海虽赊，扶摇可接。

搬运于2025-08-24 22:00:19，当前版本为作者最后更新于2019-12-21 13:31:51，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

《组合数学》原题改编石锤了（
其实此题从各方面讲都不难。

---

fibonacci 数的生成函数是这个（基础知识）

$$F(x)=\frac{x}{1-x-x^2}$$

我们知道拆分为恰好 $k$ 个数时，答案的生成函数为 $F(x)^k$
那么答案的生成函数显然为

$$G(x)=\sum_{i=0}^\infty F(x)^i$$ $$=\frac{1}{1-F(x)}=\frac{1-x-x^2}{1-2x-x^2}$$

分母写成递推式就是

$$a_n=2a_{n-1}+a_{n-2}$$

乘上分子得到答案

$$\text{ans}=a_n-a_{n-1}-a_{n-2}=a_{n-1}$$

解递推式特征方程，得

$$x_1=-\sqrt 2+1,x_2=\sqrt 2+1$$

设通项公式为

$$a_n=c_1(-\sqrt 2+1)^n+c_2(\sqrt 2+1)^n$$

分别代入 $n=0,n=1$，解得

$$\left\{\begin{aligned}c_1=\frac{\sqrt 2-1}{2\sqrt 2} \\ c_2=\frac{\sqrt 2+1}{2\sqrt 2} \end{aligned}\right. $$

注意到 $\sqrt 2$ 在模 $10^9+7$ 下存在（$59713600$），最终答案就出来了

$$a_n\equiv 485071604\times 940286408^n+514928404\times59713601^n\pmod{10^9+7} $$

直接计算即可。