[国家集训队]整数的lqp划分 题解
Problem
给你一个\(n\)
已知\(Fib_0=0,Fib_1=1,Fib_n=Fib_{n-1}+Fib_{n-2}(n>1)\)
求\(\sum\limits_{a_1+a_2+ \cdots +a_m = n}\prod\limits_{i=1}^mFib_{a_i} \mod 10^9+7\)
Solution
设数列\(b_k=\sum\limits_{a_1+a_2+ \cdots +a_m = k}\prod\limits_{i=1}^mFib_{a_i}=F(x)^k\)，所求即为\(b_n\)，我们设其生成函数为\(G(x)\)
令\(F(x)\)为\(Fibonacci\)数列的生成函数，易得\(F(x)=\frac{x}{1-x-x^2}\)
又因为\(G(x)=\sum\limits_{i=1}^{\infty}b_ix^i=\sum\limits_{i=1}^{\infty}F(x)^i=\sum\limits_{i=0}^{\infty}F(x)^i-F(x)^0\)
得到\(G(x)=\frac{1}{1-F(x)}-1=\frac{1}{1-\frac{x}{1-x-x^2}}-1=\frac{1-x-x^2}{1-2x-x^2}-1=\frac{x}{1-2x-x^2}\)
考虑到这个式子分母只有二次项，考虑暴力分解，把\(\frac{x}{1-2x-x^2}\)用待定系数法分解成\(\frac{1}{1-Ax}-\frac{1}{1-Bx}\)的形式
得到\(G(x)=\frac{\sqrt 2}{4}(\frac{1}{1-(1+\sqrt 2)x}-\frac{1}{1-(1-\sqrt 2)x})\)
展开得：\(G(x)=\sum\limits_{i=0}^{\infty}\frac{\sqrt 2}{4}((1+\sqrt 2)^i-(1-\sqrt 2)^i)x^i\)
在\(\mod 10^9+7\)意义下，\(\sqrt 2=59713600\)
故\(b_i=\frac{59713600}{4}((59713601)^i-(940286408)^i)\)
于是我们可以用\(O(logn)\)的时间内快速求出答案