[rapid_pow]斐波那契数列

思路：

练习矩阵的快速幂，就是将幂乘的指数累加过程变成变底数后指数的累乘缩小，然后在fibnaci加速就是将累次的计算（递推式的）用矩阵乘法来表示，然后就可以用乘法中的数学规律加速实现快速幂。
代码也很巧妙，就是在每一次扩大底数缩小指数的时候，若指数为奇数，这原底数肯定会被抽出一个单独乘在结果里，偶数则没有这一步，最后底数肯定会合并到指数为1的情况（或者上来就是指数为1或2的特殊情况），这个时候把这个底数抽出乘到结果里，然后底数又增大了（超出要的次数了），然后循环结束，但增大的底数并没有更新到结果，代码的出口只有每次奇数的时候更新到结果这一个出口，不管一开始是不是奇数最后都会迭代到奇数，所以代码很统一精简。

#include <iostream>
using namespace std;

class Solution {
public:
    int Fibonacci(int n) {
        int a[2][2] = {1, 1, 1, 0};
        matrix_pow(a, n);  //[fn, fn-1] = matrix^（n-1） * [1, 0] || [fn, fn-1] = matrix^(n-2) * [1, 1]，矩阵的幂运算这里可以实现求0次幂，但不能求负即逆矩阵，所以用n-1次的，即初始为1， 0的
                             //但不论初始为[1, 0]还是[1，1]第0项都是0， 第一项都是1，因为在改变初始的时候通项公式的次数也变了，整个首相是有fn fn-1 fn-2推出来
        return a[1][0]*1 + a[1][1]*0;//兼容0的情况，用第fn-1做结果
    }
    void matrix_muti(int a[][2], int b[][2]){
        int tempt[2][2] = {0};
        for(int i=0;i<2;++i){
            for(int j=0;j<2;++j){
                for(int k=0;k<2;++k){
                    tempt[i][j] += (a[i][k]*b[k][j]);
                }
            }
        }
        for(int i=0;i<2;++i){
            for(int j=0;j<2;++j){
                a[i][j] = tempt[i][j];
            }
        }
    }
    void  matrix_pow(int a[][2], int n){
        int result[2][2]={1, 0, 0, 1};//结果的出口
        while(n>0){
            if(n%2){//跟新落单的矩阵和结果
                matrix_muti(result, a);
            }
            matrix_muti(a, a);//这个只是用于下次更新，最后一次时这个算的已经超出本次范围了但不会计入result
            n /= 2;
        }
        for(int i=0;i<2;++i){
            for(int j=0;j<2;++j)
                a[i][j] = result[i][j];
        }
    }
};

还有一下fibnaci的规律，fibnaci矩阵写法有点类似通项，他的首两项是可以变的，但相应要变动矩阵的次数，然后每一个元素对应的下标是不会变的由fn，fn-1，fn-2三者关系定的（n-1次和n-2次自己都带入了一下发现0项都是0）（除非人为的推动下标，就不是最基本的fib了）