矩阵快速幂求斐波那契数列

快速幂：

1.求5^19，19个5相乘当然可以算出来，但是当指数特别大的时候O(n)就不行了，必须要O(logn)的算法，也就是根据位运算来求解。
19的二进制是（10011）
5^19=5^1 * 5^2 * 5^16;指数对应的二进制如下：
1---00001,2---00010,16---10000
于是我们可以设temp=5(底数),我们求出来的结果是ans；那么我们可以设置一个循环，起始条件是1，边界是n=5(指数的二进制的位数)，每循环一次temp就乘一次temp(乘一次就是5^2,两次就是5^4....)，同时如果此时的这一位是1，ans就乘上这个temp（根据这个步骤再结合上面的例子就可以清楚的理解代码的原理了）：

#include<stdio.h>
#define ll long long
ll qpow(ll a,ll b) {
    ll ans=1;
    while(b) {
        if(b&1)    ans*=a;//当前位置是1就乘上a（底数）
        a*=a;
        b>>=1;//b的二进制向后移一位，相当于除于2，比如10011移一次就变成了1001，可以很好的达到上述模拟的效果 
    }
    return ans;
}
ll a,b;
int main() {
    while(scanf("%lld%lld",&a,&b)==2) {
        printf("%lld\n",qpow(a,b));
    }
}

矩阵：

a[i]表示斐波那契数列第i项；a[1]=1,a[2]=1;
因为a[i]=a[i-1]+a[i-2],我们就可以尝试能不能通过矩阵相乘来求斐波那契数列，就有了下面的假设;

列出矩阵相乘的结果如下：

两个图对比发现中间矩阵非常容易求得，于是假设成立，把初始矩阵比作a(a[i]=1,a[i-1]=1)，中间矩阵比作b，求a[n]就是求a*b^(n-2)然后取第一行第一列;初始矩阵（左）和中间矩阵如下（右）：
|1 1| |1 1|
|x y| |1 0|
一般的斐波那契数列用不到x，y，所以x，y可以任意取值，这里x取1，y取0方便计算；原式就变成了a[i]=b^(n-1)然后取第一行第一列.
看到这里会发现，形如a=ax+by+k的式子，给出初始的a[0]，b[0]求a[n],都可以构建一个简单的矩阵用乘法来完成模拟，因为用乘法取模拟我们就可以用到快速幂来降低时间复杂度:

#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) {
        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;
                }
        return ans;
    }//定义了结构体后就会有这个性质   operator是是对*的重载
};
/*
* 相当于p1的一个成员函数
p1*p2相当于对象p1调用函数“operator*”，把对象p2作为一个参数传递给该函数，从而实现了两个对象的相乘。
*/
node power(node a,ll b) {
    node res;
    res.one();//单位矩阵
    while(b) {
        if(b&1)
            res=res*a;
        a=a*a;
        b>>=1;
    }
    return res;
}//快速幂求a的b次方
int main() {
    node temp;//初始矩阵
    temp.matrix[0][0]=1;    //a[2]
    temp.matrix[0][1]=1;    //a[1]
    temp.matrix[1][0]=1;
    temp.matrix[1][1]=0;
    ll n;
    while(~scanf("%lld",&n)) {
    node ans1 = power(temp,n-1);//计算出a[n]
    printf("%lld\n",ans1.matrix[0][0]);
    }
}