矩阵快速幂求斐波那契

基本形式

用矩阵分析

$\left[ \begin{matrix} F_n\\ F_n-1 \end{matrix} \right]$ $=\left[ \begin{matrix} F_n-1+F_n-2\\ F_n-1 \end{matrix} \right]$ $=\left[ \begin{matrix} 1*F_n-1+1*F_n-2\\ 1*F_n-1+0*F_n-2 \end{matrix} \right]$ $=\left[ \begin{matrix} 1&1\\ 1&0\\ \end{matrix} \right] * \left[ \begin{matrix} F_{n-1}\\ F_{n-2} \end{matrix} \right]$ $=\left[ \begin{matrix} 1&1\\ 1&0\\ \end{matrix} \right]^{n-1} * \left[ \begin{matrix} F_1\\ F_0 \end{matrix} \right]$

由上式分析可得：求F(n)等于求二阶矩阵的n - 1次方，结果取矩阵第一行第一列的元素。

快速幂优化

二阶矩阵的乘法满足结合律
设A,B,C都是任意的二阶矩阵
A(BC)=(AB)C

设n=N/2 结果向下取整

$A^N=A^n∗A^n 当n为偶数\\ A^N=A^n∗A^n∗A 当n为奇数$

相当于

$A^6=A^3*A^3\\ A^7=A^3*A^3*A$

由上式可得：通过快速幂来减少运算次数

代码

矩阵（结构体构造）

struct node
{
    LL a[2][2];//LL即long long
};

矩阵乘法

node mul(node x,node y)
{
    node z;
    memset(z.a,0,sizeof(z.a));
    for(int i=0;i<2;i++)
        for(int j=0;j<2;j++)
            for(int k=0;k<2;k++)
                z.a[i][j]=(z.a[i][j]+x.a[i][k]*y.a[k][j])%mod;
    return z;
}

求斐波那契第n个数

void quick(LL n)
{
    node c,res;
    c.a[0][0]=1,c.a[0][1]=1,c.a[1][0]=1,c.a[1][1]=0;
    res.a[0][0]=1,res.a[0][1]=0,res.a[1][0]=0,res.a[1][1]=1;
    while(n){
        if(n&1)res=mul(res,c);
        c=mul(c,c);
        n=n>>1;
    }
    //cout<<res.a[0][0]<<" "<<res.a[0][1]<<" "<<res.a[1][0]<<" "<<res.a[1][1]<<endl;
    cout<<res.a[0][1]<<endl;
}

即所求res矩阵中的a[0][1]

全部代码

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const double pi=acos(-1),eps=1e-10;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
const int m=10007;

struct node
{
    LL a[2][2];
};
LL n,sum;

node mul(node x,node y)
{
    node z;
    memset(z.a,0,sizeof(z.a));
    for(int i=0;i<2;i++)
        for(int j=0;j<2;j++)
            for(int k=0;k<2;k++)
                z.a[i][j]=(z.a[i][j]+x.a[i][k]*y.a[k][j])%mod;
    return z;
}

void quick(LL n)
{
    node c,res;
    c.a[0][0]=1,c.a[0][1]=1,c.a[1][0]=1,c.a[1][1]=0;
    res.a[0][0]=1,res.a[0][1]=0,res.a[1][0]=0,res.a[1][1]=1;
    while(n){
        if(n&1)res=mul(res,c);
        c=mul(c,c);
        n=n>>1;
    }
    //cout<<res.a[0][0]<<" "<<res.a[0][1]<<" "<<res.a[1][0]<<" "<<res.a[1][1]<<endl;
    cout<<res.a[0][1]<<endl;
}

int main()
{
    cin>>n;
    quick(n);

    return 0;
}

斐波那契数列前n项求和

$求和S_n=a_1+a_2+a_3+\ldots+a_n\\ S_n=\underline1+a_1+a_2+a_3+\ldots+a_n-\underline1\\ 由a_2=1得S_n=\underline a_2+a_1+a_2+a_3+\ldots+a_n-\underline1\\ 即S_n=\underline{a_2+a_1}+a_2+a_3+\ldots+a_n-\underline1\\ S_n=\underline a_3+a_2+a_3+\ldots+a_n-\underline1\\ 即S_n=\underline{a_3+a_2}+a_3+\ldots+a_n-\underline1\\ S_n=\underline a_4+a_3+\ldots+a_n-\underline1\\ \ldots\\ S_n=a_n+a_{n-1}+a_n-1\\ 即S_n=2*a_n+a_{n-1}-1$

斐波那契数列前n项平方求和

用几何证明

分析

$a_1^2+a_2^2=a_3*a_2\\ a_1^2+a_2^2+a_3^2=a_3*a_2+a_3^2\\ a_1^2+a_2^2+a_3^2=a_3*(a_2+a_3)\\ a_1^2+a_2^2+a_3^2=a_3*a_4\\ \ldots\\ 推导可得\\ \sum a_n=1^2+1^2+2^2+3^2+\ldots+a_n^2=a_n*a_{n+1}$

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const double pi=acos(-1),eps=1e-10;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
const int m=10007;

struct node
{
    LL a[2][2];
};
LL n,sum;

node mul(node x,node y)
{
    node z;
    memset(z.a,0,sizeof(z.a));
    for(int i=0;i<2;i++)
        for(int j=0;j<2;j++)
            for(int k=0;k<2;k++)
                z.a[i][j]=(z.a[i][j]+x.a[i][k]*y.a[k][j])%mod;
    return z;
}

void quick(LL n)
{
    node c,res;
    c.a[0][0]=1,c.a[0][1]=1,c.a[1][0]=1,c.a[1][1]=0;
    res.a[0][0]=1,res.a[0][1]=0,res.a[1][0]=0,res.a[1][1]=1;
    while(n){
        if(n&1)res=mul(res,c);
        c=mul(c,c);
        n=n>>1;
    }
    //cout<<res.a[0][0]<<" "<<res.a[0][1]<<" "<<res.a[1][0]<<" "<<res.a[1][1]<<endl;
    cout<<(res.a[0][0]%mod*res.a[0][1]%mod)%mod<<endl;
}

int main()
{
    cin>>n;
    quick(n);

    return 0;
}

即res矩阵的a[0][0]与a[0][1]相乘(注意取模)