求斐波那契前n项平方和 ——矩阵快速幂模板（几何构造证明题【附图】）

本文主要是介绍求斐波那契前n项平方和 ——矩阵快速幂模板（几何构造证明题【附图】），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

在这里插入图片描述

根据图示，我们可以知道：后面的大正方形的边长总是等于前面的小正方形组成的矩形的长；前面几个斐波那契数的平方之和（也就是前面几个小正方形的面积之和）在数值上等于最后出现的一个和下一个紧接着未出现的斐波那契数的乘积（也就是已经出现的小正方形组成的矩形的面积等于其中最大的一个小正方形的边长乘以下一个紧接着未出现的正方形的边长）。对应的公式化简后如下：
在这里插入图片描述

#include <bits/stdc++.h>
#define ll long long
#define MOD 1000000007
using namespace std;
struct nobe{ll a[2][2];};
ll n,sum;nobe mut(nobe x,nobe y)
{nobe res;memset(res.a,0,sizeof(res.a));for(ll i=0;i<2;i++)for(ll j=0;j<2;j++)for(ll k=0;k<2;k++)res.a[i][j]=(res.a[i][j]+x.a[i][k]*y.a[k][j])%MOD;return res;
}void quick(ll n)
{nobe c,res;c.a[0][0]=1;    c.a[0][1]=1;    c.a[1][0]=1;    c.a[1][1]=0;memset(res.a,0,sizeof(res.a));for(ll i=0; i<2; i++)    res.a[i][i]=1;while(n){if(n&1)res=mut(res,c);c=mut(c,c);n=n>>1;}printf("%lld\n",((res.a[0][1]%MOD)*(res.a[0][1]%MOD+res.a[1][1]%MOD))%MOD);
}int main()
{ll i,t;while(scanf("%lld",&n)!=EOF)    quick(n);return
}