斐波那契1（矩阵快速幂加速递推，斐波那契前n项平方和）

链接：登录—专业IT笔试面试备考平台_牛客网
来源：牛客网
 

Keven 特别喜欢斐波那契数列，已知 fib1=1fib_1=1fib1​=1，fib2=1fib_2=1fib2​=1，对于 n>=3n>=3n>=3，fibn=fibn−2+fibn−1fib_{n}=fib_{n-2}+fib_{n-1}fibn​=fibn−2​+fibn−1​，并且他想知道斐波那契前 nnn 项平方和是多少？

为了防止答案过大，请将最后的答案模 1e9+71e9+71e9+7

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
struct jz
{ll m[2][2];
};
jz operator * (const jz &a,const jz &b)//*，矩阵乘法的重载运算符
{jz c;memset(c.m,0,sizeof c.m);for(ll i=0;i<2;i++){for(ll j=0;j<2;j++){for(ll k=0;k<2;k++){c.m[i][j]=(c.m[i][j]+a.m[i][k]*b.m[k][j])%mod;}}}return c;
}
jz pow(jz a,ll b)
{jz res;memset(res.m,0,sizeof res.m);for(ll i=0;i<2;i++)res.m[i][i]=1;while(b){if(b&1)res=res*a;b>>=1;a=a*a;}return res;
}
ll mul(ll a,ll b,ll mod)//乘法模
{a=a%mod;b=b%mod;ll res=0;while(b){if(b&1)res=(res+a)%mod;b>>=1;a=(a+a)%mod;}return res;
}
void solve()
{ll n;cin>>n;jz ans;ans.m[0][0]=1;//赋值，先通过递推公式，确定abcd的值，d为0，其他为1ans.m[0][1]=1;ans.m[1][0]=1;ans.m[1][1]=0;jz md=pow(ans,n);cout<<mul(md.m[0][0],md.m[0][1],mod);
}
int main()
{ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);ll t=1;while(t--)solve();return 0;
}