国家集训队 的一道题。来源:2011中国国家集训队命题答辩。
题目链接:Luogu P4451。
题目
题目描述
定义斐波那契数列为 \(f _ 0=0,f _ 1=1,f _ n=f _ {n-1}+f _ {n-2},(n\geq 2)\)。
给定 \(n\),求
\[\sum(\prod^m _ {i=1}f _ {a _ i})\]
其中
\[
\begin{cases}
m>0\\
a _ 1,a _ 2,\cdots,a _ m>0\\
n=\sum^m _ {i=1}a _ i
\end{cases}
\]
由于答案可能非常大,所以要对 \(10^9+7\) 取模。
数据范围
对于 \(60\%\) 的数据,\(1\leq n\leq 10^9\);
对于 \(100\%\) 的数据,\(1\leq n\leq 10^{10000}\)。
时空限制
题目编号 | 时间限制 | 空间限制 |
Luogu P4451 | \(1\text{s}\) | \(125\text{MiB}\) |
题解
本题有多种做法,下面仅介绍最高效的一种。
前置知识
- 生成函数;
- 特征方程求数列通项。
思路
首先根据生成函数相关知识我们知道,斐波那契数列的生成函数
\[F(x)=\frac{x}{1-x-x^2}\]
然后考虑本题答案的生成函数,当 \(m\) 一定时,不难发现答案的生成函数是
\[\texttt{ans} _ m(x)=(f(x))^m\]
那么推出答案为
\[
\begin{aligned}
\texttt{ans}(x)&=\sum _ {i=0}(f(x))^i\\
&=\frac{1}{1-f(x)}\\
&=\frac{1-x-x^2}{1-2x-x^2}
\end{aligned}
\]
根据分母求出新数列的递推公式
\[a _ n=2a _ {n-1}+a _ {n-2}\]
再由分子写出答案
\[\texttt{ans}=a _ n-a _ {n-1}-a _ {n-2}=a _ {n-1}\]
再通过特征方程求数列通项的方法我们可以求出
\[a _ n=\frac{2-\sqrt{2}}{4}(-\sqrt{2}+1)^n+\frac{2+\sqrt{2}}{4}(\sqrt{2}+1)^n\]
又因为
\[59713600^2\equiv 2\pmod{10^9+7}\]
所以
\[
\begin{aligned}
\texttt{ans}&=a _ {n-1}\\
&\equiv 485071604\times 940286408^{n-1}+514928404\times 59713601^{n-1}
\end{aligned}
\]
代码
#include<bits/stdc++.h> using namespace std; #define reg register typedef long long ll; const int MOD=1e9+7; #define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++) static char buf[100000],*p1=buf,*p2=buf; inline int read(void){ reg char ch=getchar(); reg int res=0; while(ch<'0'||'9'<ch)ch=getchar(); while('0'<=ch&&ch<='9')res=(10ll*res+ch-'0')%(MOD-1),ch=getchar(); return res; } int n; inline int pow(reg int x,reg int exp,reg int mod){ reg int res=1; while(exp){ if(exp&1) res=1ll*res*x%mod; x=1ll*x*x%mod; exp>>=1; } return res; } int main(void){ n=read(); reg int ans=(485071604ll*pow(940286408,(n-1+MOD-1)%(MOD-1),MOD)%MOD+514928404ll*pow(59713601,(n-1+MOD-1)%(MOD-1),MOD)%MOD)%MOD; printf("%d\n",ans); return 0; }
近期评论