用矩阵快速幂求解递推数列的第n项

斐波那契数列

  • 每一项的数字等于前两项的和, f_0=0, f_1 =1, f_2=1
  1. 递推公式
    f_i = f_{i-1} + f_{i-2}
  2. 矩阵形式
    [f_i,f_{i-1}] = [f_{i-1}, f_{i-2}] * \begin{bmatrix} 1&1 \\ 1& 0 \end{bmatrix} = [1, 0] * \begin{bmatrix} 1&1 \\ 1& 0 \end{bmatrix} ^ {i-1}

击鼓传花

  • 题目描述:
    一共有k个人, 每一次可以把自己手中的花传给其它任何一个人, 初始时在自己手中, 求M次后有多少种方式回到自己手中
  1. 递推公式
    a_i表示第i次在自己手中, b_i表示第i次不在自己手中, a_0=1, b_0=0
  2. 矩阵形式
    [a_i,b_i] = [a_{i-1}, b_{i-1}] * \begin{bmatrix} 0&k-1 \\ 1& k-2 \end{bmatrix} = [1, 0] * \begin{bmatrix} 0&k-1 \\ 1& k-2 \end{bmatrix} ^ i

求数列的第n项

  1. 递推公式
    f_i = a f_{i-1} + bf_{i-2} + c f_{i-3} + 2 i^2 - i + 32767

  2. 矩阵形式
    [f_i, f_{i-1}, f_{i-2}, (i+1)^2, i+1, 1] = [f_{i-1}, f_{i-2}, f_{i-3}, i^2, i, 1] * \begin {bmatrix} a & 1 & 0 & 0 & 0 & 0\\ b & 0 & 1 & 0 & 0 & 0\\ c & 0 & 0 & 0 & 0 & 0\\ 2 & 0 & 0 & 1 & 0 & 0\\ -1 & 0 & 0 & 2 & 1 & 0\\ 32767 & 0 & 0 & 1 & 1 & 1 \end {bmatrix}
    首先将向量改写成concat([f_{i-1}, f_{i-2}, \cdots, f_0],[i^t, i ^{t-1}, \cdots, i, 1])的形式, 即向量中只有系数为1数列的前几项或者i的多项式, 然后待定系数求转移矩阵

矩阵快速幂的参考代码


public class MatQuickPower {

    public static final int MOD = 1_000_000_007;

    public static int[][] matQuickPower(int [][]a, int k) {
        if (k == 1) return a;
        int [][]tmp = matQuickPower(a, k >> 1);
        if ((k & 1) == 0) return matmul(tmp, tmp);
        else return matmul(matmul(tmp, tmp), a);
    }

    public static int[][] matmul(int [][]a, int [][]b) {
        int [][]c = new int[a.length][b[0].length];
        for (int i = 0; i < a.length; i++) {
            for (int j = 0; j < b[0].length; j++) {
                for (int k = 0; k < a[i].length; k ++){
                    c[i][j] = (int) ((c[i][j] + (long)(a[i][k] % MOD) * (long)(b[k][j] % MOD)) % MOD);
                }
            }
        }
        return c;
    }

}
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成，浏览时请结合常识与多方信息审慎甄别。
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

相关阅读更多精彩内容

友情链接更多精彩内容