矩阵快速幂技巧练习（一）— 经典牛问题

上一篇文章简单介绍了斐波那契数列的矩阵乘法，并做了一个小推广，这篇文章来小试牛刀，做一个经典的练习题。
求斐波那契数列矩阵乘法的方法

题目
第一年农场有一只成熟的母牛A，往后的每年：

1. 每一只成熟的母牛都会生一只母牛
2. 每一只新出生的母牛都会在第三年成熟。
3. 每一只母牛都不会死。

求n年后牛的数量。

---

先来看一下农场前6年牛的变化。
解释一下，第一年只有牛A。
第二年牛A生了牛B。
第三年牛A生了牛C，因为牛B还不成熟，所以只能A生。
第四年依然是牛A生了牛D。
第五年，此时牛B也已经成熟，并且牛不会死，所以牛A继续生牛E，牛B生牛F。
第六年，前几年的牛继续保留，此时C也成熟可以生小牛，所以ABC分别生3只小牛。

根据题意可推导出：新的一年中，我每年都要保留前一年的所有牛，并且3年前的牛已经成熟可以生新的小牛，所以3年前有多少头牛，就生多少头牛。
所以：$F(n)=F(n?1)+F(n?3)$。

---

根据上面公式可以看出它是一个3阶的递推式，所以下面的式子它一定满足：

$$|F_4,F_3,F_2|=|F_3,F_2,F_1|\times \left|\begin{array}{ccc}a& b& c\\ d& e& f\\ g& h& i\end{array}\right|$$

$$|F_5,F_4,F_3|=|F_4,F_3,F_2|\times \left|\begin{array}{ccc}a& b& c\\ d& e& f\\ g& h& i\end{array}\right|$$
$$|F_n,F_{n?1},F_{n?2}|=|F_3,F_2,F_1|\times {\left|\begin{array}{ccc}a& b& c\\ d& e& f\\ g& h& i\end{array}\right|}^{n?3}$$

所以我们只要先根据给定的初始值，来求出固定的 3 * 3矩阵，再将n- 2次方带入。就能够求出来Fn的值。

---

初始值我们知道 F(1) = 1，F(2) = 2，F(3) = 3，F(4) = 4，F(5) = 6，F(6) = 9，如果初始值不够求出矩阵，那就根据公式$F(n)=F(n?1)+F(n?3)$继续带入，获取更多值的信息。

$$|F_4,F_3,F_2|=|F_3,F_2,F_1|\times \left|\begin{array}{ccc}a& b& c\\ d& e& f\\ g& h& i\end{array}\right|?>|4,3,2|=|3,2,1|\times \left|\begin{array}{ccc}a& b& c\\ d& e& f\\ g& h& i\end{array}\right|$$
继续带入
$$?\begin{array}{l}3a+2d+g=4\\ 3b+2e+h=3\\ 3c+2f+i=2\end{array}\text{\hspace{1em}(1)}$$
一个式子求不出来，在带入其他式子
$$|F_5,F_4,F_3|=|F_4,F_3,F_2|\times \left|\begin{array}{ccc}a& b& c\\ d& e& f\\ g& h& i\end{array}\right|?>|6,4,3|=|4,3,2|\times \left|\begin{array}{ccc}a& b& c\\ d& e& f\\ g& h& i\end{array}\right|$$
$$?\begin{array}{l}4a+3d+2g=6\\ 4b+3e+2h=4\\ 4c+3f+2i=3\end{array}\text{\hspace{1em}(2)}$$
以此类推，不一一列举，最后求出来矩阵的值为：
$$\left|\begin{array}{ccc}1& 1& 0\\ 1& 0& 1\\ 0& 0& 1\end{array}\right|$$

---

接下来求矩阵的n - 2次方的值。

代码

public static int c1(int n){
        if(n < 1){
            return 0;
        }

        if (n == 1 || n == 2 || n == 3){
            return n;
        }
        int[][] base = {{1,1,0},
                        {1,0,1},
                        {0,0,1}};

        int[][] res = matrixPower(base,n - 3);
        return 3 * res[0][0] + 2 * res[1][0] + res[2][0];
    }
    
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) {
                res = product(res, t);
            }
            t = product(t, t);
        }
        return res;
    }

    // 两个矩阵乘完之后的结果返回
    public static int[][] product(int[][] a, int[][] b) {
        int n = a.length;
        int m = b[0].length;
        int k = a[0].length; // a的列数同时也是b的行数
        int[][] ans = new int[n][m];
        for(int i = 0 ; i < n; i++) {
            for(int j = 0 ; j < m;j++) {
                for(int c = 0; c < k; c++) {
                    ans[i][j] += a[i][c] * b[c][j];
                }
            }
        }
        return ans;
    }