Description
求
\[\begin{aligned}
& \sum \prod_{i=1}^m F_{a_i} \\
& m>0 \\
& a_1, a_2 \ldots a_m>0 \\
& a_1+a_2+\ldots+a_m=n
\end{aligned}
\]
由于答案可能非常大，所以要对 \(10^9+7\) 取模。
Solution
题目中有整数拆分的部分，可以想到用生成函数的相关知识。
设斐波那契数列的生成函数 \(F(x)=f_0+f_1x+f_2x^2+\dots\)。
那么有
\[\begin{aligned}F(x)&=f_0+f_1x+f_2x^2+f_3x^3+\dots\\xF(x)&=\ \ \ \ \ \ \ \ f_0x+f_1x^2+f_2x^3+\dots\\x^2F(x)&=\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ f_0x^2+f_1x^3+\dots\end{aligned}
\]
相减可以得到 \(F(x)=\dfrac{x}{1-x-x^2}\)。
那么本题的答案序列的生成函数 \(G(x)=\sum_{m=0}^{\infty}F(x)^m\)。
因为如果拆分成 \(m\) 个数，那么每个位置上的选择的生成函数都是 \(F(x)\)，相乘即可就是 \(F(x)^m\)。
\[\begin{aligned}G(x)&=\sum_{m=0}^{\infty}F(x)^m\\&=\dfrac{1}{1-F(x)}\\&=\dfrac{1}{1-\frac{x}{1-x-x^2}}\\&=\dfrac{1-x-x^2}{1-2x-x^2}\\&=1+\dfrac{x}{1-2x-x^2}\\&=1+\dfrac{x}{\left[1-(1+\sqrt2)x\right]\left[1-(1-\sqrt2)x\right]}\\&=1+\dfrac{1}{2\sqrt2}\left(\dfrac{1}{1-(1+\sqrt2)x}-\dfrac{1}{1-\left(1-\sqrt2\right)x}\right)\\&=1+\dfrac{1}{2\sqrt2}\left(\sum^{\infty}_{n=0}\left(1+\sqrt2\right)^nx^n-\sum_{n=0}^{\infty}\left(1-\sqrt2\right)^nx^n\right)\\&=1+\sum_{n=0}^{\infty}\dfrac{\sqrt2}{4}\cdot\left[\left(1+\sqrt2\right)^n-\left(1-\sqrt2\right)^n\right]x^n\end{aligned}
\]
那么答案 \(ans_n=\dfrac{\sqrt2}{4}\cdot\left[\left(1+\sqrt2\right)^n-\left(1-\sqrt2\right)^n\right]\)。
另外，\(2\) 在模 \(10^9+7\) 意义下的二次剩余是 \(59713600\)，换个好理解的方式，即 \(\sqrt2 \mod 10^9+7=59713600\)。
Code
#include<cstdio>
#define N
#define mod 1000000007
#define ll long long
using namespace std;
ll n,sqrt2=59713600,ans;
ll read()
{
ll res=0;char ch=getchar();
while (ch<'0'||ch>'9') continue;
while (ch>='0'&&ch<='9')
{
res=(res*10%(mod-1)+(ch-'0'))%(mod-1);
ch=getchar();
}
return res;
}
ll ksm(ll x,ll y)
{
ll res=1;
while (y)
{
if (y&1) res=res*x%mod;
x=x*x%mod;
y>>=1;
}
return res;
}
int main()
{
n=read();
ans=sqrt2*ksm(4,mod-2)%mod*(ksm(sqrt2+1,n)-ksm(-sqrt2+1+mod,n)+mod)%mod;
printf("%lld\n",ans);
return 0;
}