题解 P4451 【[国家集训队]整数的lqp拆分】

· · 题解

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

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}

直接计算即可。