斐波那契数列
- 每一项的数字等于前两项的和,
- 递推公式
- 矩阵形式
击鼓传花
- 题目描述:
一共有k个人, 每一次可以把自己手中的花传给其它任何一个人, 初始时在自己手中, 求M次后有多少种方式回到自己手中
- 递推公式
表示第
次在自己手中,
表示第
- 矩阵形式
求数列的第n项
递推公式
矩阵形式
首先将向量改写成的形式, 即向量中只有系数为1数列的前几项或者
矩阵快速幂的参考代码
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;
}
}
