【题解】Fibonacci前n项和

题目大意

大家知道Fibonacci数列吧，f[1]=1,f[2]=1,f[3]=2,f[4]=3……也就是f[n]=f[n-1]+f[n-2]。现在问题很简单，输入n和m，求前n项和取模m。

数据范围

1<=n<=2000000000 1<=m<=1000000010

分析

数据范围很大，所以递推肯定是会爆炸的。

我们考虑用矩阵优化，（没有做过斐波那契数列？那还不快去做！）但是，这下又出现了一个问题，那就是我们如果直接用矩阵乘法的话只能求出一个数列的第n项，如何求出前n项的和......嗯，这是个问题。

但是，出题人是不可能自己坑害自己的！所以，这其中肯定是有什么规律可言。

我们发现：

\[dp[i]=dp[i-1]+dp[i-2] \]

那么，对于\(dp[n]\),我们能知道：

\[dp[n]=dp[n-1]+dp[n-2]=dp[n-2]+dp[n-3]+dp[n-3]+dp[n-4]=dp[n-2]+dp[n-3]+......=dp[1]+\sum _{i=1}^{n-2} dp[i] \]

也就是说，我们求出来的第n项，其实就是\(dp[1]到dp[n-2]\)的和再加上1。

这就好办了，我们只要求出第n+2项的值再减去1即可。

code:

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long ll;
ll n,m;
struct Matrix {
	ll mat[2][2];
	void clear() {
		memset(mat,0,sizeof(mat));
	}
	void idenaty() {
		clear(); 
		for(int i=0;i<2;i++) 
			mat[i][i]=1;
	} 
};
Matrix mul(Matrix a,Matrix b) {
	Matrix res;
	res.clear();
	for(int i=0;i<2;i++) {
		for(int j=0;j<2;j++) {
			for(int k=0;k<2;k++) {
				res.mat[i][j]=(res.mat[i][j]+a.mat[i][k]*b.mat[k][j]%m)%m;
			}
		}
	}
	return res;
}
Matrix power(Matrix x,ll p) {
	Matrix res;
	res.idenaty();
	while(p) {
		if(p&1) res=mul(res,x);
		x=mul(x,x);
		p>>=1;
	}
	return res;
}
Matrix a;
int main() {
	scanf("%lld%lld",&n,&m);
	a.mat[0][0]=1,a.mat[0][1]=1;
	a.mat[1][0]=1,a.mat[1][1]=0;
	Matrix res=power(a,n+1);//求出第n+2项
	printf("%lld",res.mat[0][0]-1);
	return 0;
}
/*
dp[i]= 1 * dp[i-1] + 1*dp[i-2]
dp[i-1]= 1 * dp[i-1] + 0*dp[i-2]
*/