「题解」「国家集训队答辩 2011」整数的 lqp 拆分

国家集训队 的一道题。来源：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;
}

相关题目

• 「题解」「国家集训队」middle；
• 「题解」「国家集训队」整数的 lqp 拆分。