斐波那契

小白月赛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);
    }
}