小白月赛20
戳我传送
题目大意:
输出前斐波那契数列前n项平方和,1<=n<=1e18。
前备知识:
快速幂和矩阵,可以进我的博客了解一下,小白非常容易理解:
戳我了解
思路:
斐波那契数列前n项平方和有递推式:前n项平方和等于 f[n] * f[n+1]。
因为n非常大,用递归的思路去求肯定超时,所以想办法用 (log n)的方法去解,用矩阵转化为乘法,然后快速幂求解就可以了。
一道模板题,难度适宜。
Code:
(那个时候学的代码)
#include<bits/stdc++.h> #define ll long long using namespace std; const ll mod = 1e9 + 7; struct node { ll matrix[2][2];//结构体中的矩阵 node()//定义了结构体后会自动初始化 { memset(matrix,0,sizeof(matrix)); } void one()//单位矩阵 { matrix[0][0]=1; matrix[1][1]=1; } node operator*(node other)//定义了结构体后就会有这个性质 operator是是对*的重载 { node ans;//记录乘积 for(int i=0; i<2; i++) for(int j=0; j<2; j++) for(int k=0; k<2; k++) { ans.matrix[i][j] += matrix[i][k]*other.matrix[k][j]; ans.matrix[i][j]%=mod-1; } return ans; } }; /* * 相当于p1的一个成员函数 p1*p2相当于对象p1调用函数“operator*”,把对象p2作为一个参数传递给该函数,从而实现了两个对象的相乘。 */ node power(node a,ll b)//快速幂求a的b次方 { node res; res.one();//单位矩阵 while(b) { if(b&1)//b为奇数时乘底数 res=res*a; a=a*a; b>>=1;//b向后移 } return res; } int main() { node real;//取a[n-1]+a[n-2]; real.matrix[0][0]=1; real.matrix[0][1]=0; real.matrix[1][0]=1; real.matrix[1][1]=0; node temp;//取到a[2] a[1],并有a[n-1]+a[n-2]和保存a[n-1]的功能 temp.matrix[0][0]=1; temp.matrix[0][1]=1; temp.matrix[1][0]=1; temp.matrix[1][1]=0; ll n; scanf("%lld",&n); if(n==1) printf("1\n"); else { node ans1 = power(temp,n-2)*real;//计算出a[n] node ans2 = power(temp,n-1)*real;//计算出a[n+1] printf("%lld\n",ans1.matrix[0][0]*ans2.matrix[0][0]%mod); } }