【剑指offer】斐波那契数列

根据递推公式构造系数矩阵用于快速幂（竞赛中经常用到）
进阶博客：https://blog.csdn.net/u012061345/article/details/52224623#commentBox

class Mat { // 矩阵对象
    int n = 2;
    int m[][] = new int[n][n];

    public Mat mul(Mat a) { // 矩阵乘法
        Mat b = new Mat();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++)
                for (int k = 0; k < n; k++)
                    b.m[i][j] += this.m[i][k] * a.m[k][j];
        }
        return b;
    }
}

public class Solution {
    public static int Fibonacci(int n) {
        if(n==0){
            return 0;
        }

        Mat ans = new Mat();
        for (int i = 0; i < ans.n; i++) { //单位矩阵初始化
            ans.m[i][i] = 1;
        }
        Mat base = new Mat();
        base.m[0][0] = base.m[0][1] = base.m[1][0] = 1; // base矩阵初始化
        base.m[1][1] = 0;

        n -= 1;
        while (n > 0) { // 快速幂：求base矩阵的n-1次方
            if ((n & 1) != 0) {
                ans = ans.mul(base);
            }
            n >>= 1;
            base = base.mul(base);
        }
        return ans.m[0][0];

    }
}