斐波那契數(shù)列
- 每一項(xiàng)的數(shù)字等于前兩項(xiàng)的和,
- 遞推公式
- 矩陣形式
擊鼓傳花
- 題目描述:
一共有k個(gè)人, 每一次可以把自己手中的花傳給其它任何一個(gè)人, 初始時(shí)在自己手中, 求M次后有多少種方式回到自己手中
- 遞推公式
表示第
次在自己手中,
表示第
- 矩陣形式
求數(shù)列的第n項(xiàng)
遞推公式
矩陣形式
首先將向量改寫成的形式, 即向量中只有系數(shù)為1數(shù)列的前幾項(xiàng)或者
矩陣快速冪的參考代碼
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;
}
}
