快速幂 + 数学

首先 用数学归纳法证明
斐波那契数列前n项平方和 等于 f[n] * f[n+1];
假设 第 n 项时满足 前n项平方和 等于 f[n] * f[n+1];
那么 第 n+1 项时 应该是
f[n] * f[n+1] + f[n+1] * f[n+1]
= f[n+1] * (f[n] + f [n+1] )
= f[n+1] * f[n+2] = 假设的情况
且 第 1 项 平方和 满足
证毕
定义 一个列向量 存放 (f[n+1] f[n] )T
根据矩阵的乘法性质 可以看出
1 1
1 0
这个矩阵乘以 列向量 (f[n+1] f[n])T 就等于 (f[n+2] f[n+1])T
所以 (f[n+1] f[n]) T
就等于 有 n-1 个
1 1
1 0
于 (f[2] f[1])T左乘
根据 矩阵 的结合率
可以先算二阶矩阵的乘积再与 (f[2] f[1])T左乘
就相当于 求 一个矩阵的n-1次 再乘以 一个列向量
可以定义一个结构体存放 二阶矩阵
1 1
1 0
然后 重载乘法 变成矩阵的乘法
再根据 非递归的快速幂 方法快速求出矩阵的n-1次

#include <stdio.h>
typedef long long ll;
const int mod = 1e9 + 7;
struct  Node {
    ll a[2][2] = {{1,1},{1,0}};
    Node operator* ( Node b ) { //重载乘号 
        Node x;
        x.a[0][0] = ( this->a[0][0] * b.a[0][0] ) % mod + ( this->a[0][1] * b.a[1][0] ) % mod;  
        x.a[0][1] = ( this->a[0][0] * b.a[0][1] ) % mod + ( this->a[0][1] * b.a[1][1] ) % mod;  
        x.a[1][0] = ( this->a[1][0] * b.a[0][0] ) % mod + ( this->a[1][1] * b.a[1][0] ) % mod;  
        x.a[1][1] = ( this->a[1][0] * b.a[0][1] ) % mod + ( this->a[1][1] * b.a[1][1] ) % mod; 
        return x;
    } 
}; 
/**
 *快速幂的非递归写法 只不过把数换成了矩阵 
 **/
Node quick ( Node a ,ll ans ) 
{ 
    if ( ans == 1) {
        return a;
    }  
    Node x ;
    ans--;
    while ( ans ) {
        if ( ans & 1 ) {
            x = x * a;
        }
        a = a * a;
        ans >>= 1 ;
    }
    return x;
}
int main()
{
    Node a ;
    ll n;
    scanf ("%lld", &n);
    if ( n == 1 ||  n == 2 ) {
        printf ("%lld\n",n);
        return 0;
    }
    a = quick ( a , n - 1 );     
    Node f ;
    f = f * a;
    ll fin = ( f.a[0][0] * f.a[1][0] ) % mod ;
    printf ("%lld\n",fin );
    return 0;
}