#特征方程，dp，快速幂#洛谷 4451 [国家集训队]整数的lqp拆分

题目

---

分析

设(dp[n])表示答案，因为(dp[n]=sumprod_{i=1}^mF_{a_i})
(dp[n]=sum_{i=1}^{n-1}dp[i]*F_{n-i-1})
那么(dp[i+1]-dp[i]=sum_{j=1}^idp[j]*F_{i-j+1}-sum_{j=1}^{i-1}dp[j]*F_{i-j})
(=dp[i]+sum_{j=1}^{i-1}dp[j]*(F_{i-j+1}-F_{i-j})=dp[i]+sum_{j=1}^{i-1}dp[j]*F_{i-j-1})
因为当(j=i-1)时，(F_{i-j-1}=F_{0}=0)，所以(=dp[i]+sum_{j=1}^{i-2}dp[j]*F_{i-1-j}=dp[i]+dp[i-1])
所以(dp[i+1]=2*dp[i]+dp[i-1])，上面推导可以用生成函数做，不过我不会
其实我好像去年已经写了弱化版((nleq 10^6))，结果现在数据范围加强到(nleq 10^{10000})
因为知道(dp[0]=0,dp[1]=1)（废话），所以其实可以用矩阵乘法写，不过常数好像有点点大
考虑利用特征方程求解，用待定系数法，设其满足
(dp[n+1]-a*dp[n]=b(dp[n]-a*dp[n-1]))
套一套上式(dp[n+1]-dp[n]=dp[n]-dp[n-1])
那么其实(a=1,b=1)，且(dp[n+1]-(a+b)dp[n]-ab*dp[n-1]=0)
由于((a+b)=2,-ab=-1)，所以其实解的是(x^2-2x-1=0)的方程的解
得到两个实数根分别为(x_1=1+sqrt{2},x_2=1-sqrt{2})
答案就是

[dp[n]=frac{dp[1]-x_2dp[0]}{x_1-x_2}{x_1}^n+frac{dp[1]-x_1dp[0]}{x_2-x_1}{x_2}^n ]

代入(x_1,x_2)并化简可以得到

[dp[n]=frac{(1+sqrt{2})^n-(1-sqrt{2})^n}{2sqrt{2}} ]

而且(sqrt{2})在模(10^9+7)的意义下等同于(59713600)
况且还有费马小定理，就可以(O(log_2mod))求解啦

---

代码

#include <cstdio>
#include <cctype>
#include <algorithm>
#define rr register
using namespace std;
const int mod=1e9+7,sqrt2=59713600,inv=14928400;
inline signed iut(){
	rr int ans=0; rr char c=getchar();
	while (!isdigit(c)) c=getchar();
	while (isdigit(c)) ans=(ans*10ll+c-48)%(mod-1),c=getchar();
	return ans;
}
inline signed ksm(int x,int y){
	rr int ans=1;
	for (;y;y>>=1,x=1ll*x*x%mod)
	    if (y&1) ans=1ll*ans*x%mod;
	return ans;
}
inline signed mo2(int x,int y){return x<y?x-y+mod:x-y;}
signed main(){
	rr int n=iut(),A=sqrt2+1,B=mod-sqrt2+1;
	return !printf("%d",1ll*inv*mo2(ksm(A,n),ksm(B,n))%mod);
}