15. 矩阵快速幂技巧

没有条件转移的严格递推式，求第N项的结果，都有logN的时间复杂度的方式。
如：斐波那契数列的严格递推公式为：

当含有条件转移的递推式，求第N项的结果，没有logN时间复杂度的方式
eg:
当为true时，为一个计算公式：
当为false时，为另外一个计算公式

线性代数解决严格递归，第几个项的问题

斐波那契数列减的最多项为2，为2阶递推，则会存在一个二阶base矩阵，对于下列任意一项都满足

…….

将第一个式子中的 |F3,F2| 带入到 第二个式子|F3,F2|中，依次带入第三个，一直到带入最后一个式子中，得到最后结果为：

则只要求出 矩阵的m次幂，则就可以推出第n项的值。

如何求一个常数的n次幂，如，75=64+8+2+1用二进制表示为：1001011
则 = 1

同理对于一个矩阵|A|求其75次幂，按照上述规则，将1换成单位矩阵，10换成矩阵A即可。

题目1：
斐波那契数列求解第N项， LogN的时间复杂度。

// ################################# 题目1 斐波那契 #####################
    public static int f1(int n) {
        if (n < 1) {
            return 0;
        }
        if (n == 1 || n == 2) {
            return 1;
        }
        return f1(n - 1) + f1(n - 2);
    }
    public static int f2(int n) {
        if (n < 1) {
            return 0;
        }
        if (n == 1 || n == 2) {
            return 1;
        }
        int res = 1;
        int pre = 1;
        int tmp = 0;
        for (int i = 3; i <= n; i++) {
            tmp = res;
            res = res + pre;
            pre = tmp;
        }
        return res;
    }
    // O(logN)  矩阵快速幂技巧.求斐波那契额数列
    public static int f3(int n) {
        if (n < 1) {
            return 0;
        }
        if (n == 1 || n == 2) {
            return 1;
        }
        // 数学计算求出base矩阵，
        int[][] base = { 
                { 1, 1 }, 
                { 1, 0 } 
                };
        int[][] res = matrixPower(base, n - 2);// 斐波那契base矩阵的n-2次幂，结果还是二维矩阵.
        return 1 * res[0][0] + 1 * res[1][0];             //  |F(n),F(n-1)| = |F(2),F(1)| * |x,y|
                                                                //                          |t,z|
    }
    // 求某个矩阵的p次幂
    public static int[][] matrixPower(int[][] m, int p) {
        int[][] res = new int[m.length][m[0].length];
        for (int i = 0; i < res.length; i++) {
            res[i][i] = 1;  // 单位矩阵
        }
        // res = 矩阵中的1
        int[][] t = m;// 矩阵1次方
        for (; p != 0; p >>= 1) {
            if ((p & 1) != 0) {  // 最末尾有1
                res = muliMatrix(res, t);
            }
            t = muliMatrix(t, t);
        }
        return res;
    }
    // 两个矩阵相乘之后的结果返回
    public static int[][] muliMatrix(int[][] m1, int[][] m2) {
        int[][] res = new int[m1.length][m2[0].length];
        for (int i = 0; i < m1.length; i++) {
            for (int j = 0; j < m2[0].length; j++) {
                for (int k = 0; k < m2.length; k++) {
                    res[i][j] += m1[i][k] * m2[k][j];
                }
            }
        }
        return res;
    }

题目2：
母牛生小牛问题，求N年后牛的总数。

/**
     * 第一年农场有1只成熟的母牛A，往后的每年：
     * 1）每一只成熟的母牛都会生一只母牛
     * 2）每一只新出生的母牛都在出生的第三年成熟
     * 3）每一只母牛永远不会死
     * 返回N年后牛的数量。
     */
    public static int c1(int n) {
        if (n < 1) {
            return 0;
        }
        if (n == 1 || n == 2 || n == 3) {
            return n;
        }
        return c1(n - 1) + c1(n - 3);
    }
    public static int c2(int n) {
        if (n < 1) {
            return 0;
        }
        if (n == 1 || n == 2 || n == 3) {
            return n;
        }
        int res = 3;
        int pre = 2;
        int prepre = 1;
        int tmp1 = 0;
        int tmp2 = 0;
        for (int i = 4; i <= n; i++) {
            tmp1 = res;
            tmp2 = pre;
            res = res + prepre;
            pre = tmp1;
            prepre = tmp2;
        }
        return res;
    }
    public static int c3(int n) {
        if (n < 1) {
            return 0;
        }
        if (n == 1 || n == 2 || n == 3) {
            return n;
        }
        // base系数矩阵
        int[][] base = { 
                { 1, 1, 0 }, 
                { 0, 0, 1 }, 
                { 1, 0, 0 } };
        int[][] res = matrixPower(base, n - 3);
        return 3 * res[0][0] + 2 * res[1][0] + res[2][0];