因为结合律的存在，所以能进行矩阵快速幂

剑指 Offer 10- I. 斐波那契数列

写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项（即 F(N)）。斐波那契数列的定义如下：
F(0) = 0, F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

示例 1：
输入：n = 2
输出：1

示例 2：
输入：n = 5
输出：5


提示：

  • 0 <= n <= 100

思路：
矩阵快速幂

Acwing 1303. 斐波那契前 n 项和

大家都知道 Fibonacci 数列吧，f1=1,f2=1,f3=2,f4=3,…,fn=fn−1+fn−2
现在问题很简单，输入 n 和 m，求 fn 的前 n 项和 Snmodm。
输入格式
共一行，包含两个整数 n 和 m。
输出格式
输出前 n 项和 Snmodm 的值。
数据范围
1≤n≤2000000000
1≤m≤1000000010
输入样例：
5 1000
输出样例：
12

思路：
矩阵快速幂

  1. /*
  2.     Fn =     [fn, f(n+1), sn]
  3.     F(n+1) = [f(n+1), f(n+2), s(n+1)]
  4.     F(n+1) = Fn * [
  5.                     [0, 1, 0]
  6.                     [1, 1, 1]
  7.                     [0, 0, 1]
  8.                 ]
  10. */
  11. import java.util.*;
  13. public class Main {
  14.     static final int N = 3;
  15.     static int n, mod;
  17.     public static void main(String[] args) {
  18.         Scanner sc = new Scanner(System.in);
  19.         n = sc.nextInt();
  20.         mod = sc.nextInt();
  22.         int[][] f1 = {{1, 1, 1}};
  23.         int[][] b = {
  24.             {0, 1, 0},
  25.             {1, 1, 1},
  26.             {0, 0, 1}
  27.         };
  29.         n--;
  30.         while (n > 0) {
  31.             if ((n & 1) == 1) {
  32.                 mul(f1, f1, b);
  33.             }
  34.             n >>= 1;
  35.             mul(b, b, b);
  36.         }
  37.         System.out.println(f1[0][2]);
  38.     }
  40.     static void mul(int[][] c, int[][] a, int[][] b) {
  41.         int x = a.length, y = a[0].length, z = b.length;
  42.         int[][] res = new int[x][y];
  44.         for (int i = 0; i < x; i++) {
  45.             for (int j = 0; j < y; j++) {
  46.                 long sum = 0;
  47.                 for (int k = 0; k < z; k++)
  48.                     sum += 1L * a[i][k] * b[k][j];
  49.                 res[i][j] = (int)(sum % mod);
  50.             }
  51.         }
  52.         for (int i = 0; i < x; i++)
  53.             for (int j = 0; j < y; j++)
  54.                 c[i][j] = res[i][j];
  55.     }
  56. }

AcWing 1217. 垒骰子

思路：
矩阵快速幂

  1. import java.util.*;
  3. public class Main {
  4.     static final int MOD = (int)(1e9 + 7);
  5.     static int[] map = {3, 4, 5, 0, 1, 2};
  6.     static int[][] cof = new int[6][6];
  7.     static int[][] f = new int[6][6];
  8.     static int n, m;
  9.     public static void main(String[] args) {
  10.         Scanner sc = new Scanner(System.in);
  11.         n = sc.nextInt();
  12.         m = sc.nextInt();
  14.         Arrays.fill(f[0], 4);
  15.         for (int i = 0; i < 6; i++) {
  16.             Arrays.fill(cof[i], 4);
  17.         }
  18.         while (m-- > 0) {
  19.             int x = sc.nextInt(), y = sc.nextInt();
  20.             x--;
  21.             y--;
  22.             cof[x][map[y]] = 0;
  23.             cof[y][map[x]] = 0;
  24.         }
  26.         n--;
  27.         while (n > 0) {
  28.             if ((n & 1) == 1) {
  29.                 mul(f, f, cof);
  30.             }
  31.             n >>= 1;
  32.             mul(cof, cof, cof);
  33.         }
  35.         long res = 0;
  36.         for (int i = 0; i < 6; i++)
  37.             res = (res + f[0][i]) % MOD;
  38.         System.out.println(res);
  39.     }
  41.     static void mul(int[][] c, int[][] a, int[][] b) {
  42.         int n = c.length, m = c[0].length, size = b.length;
  43.         long[][] res = new long[n][m];
  45.         for (int k = 0; k < size; k++) {
  46.             for (int i = 0; i < n; i++) {
  47.                 for (int j = 0; j < m; j++) {
  48.                     res[i][j] = (res[i][j] + 1L * a[i][k] * b[k][j]) % MOD;
  49.                 }
  50.             }
  51.         }
  53.         for (int i = 0; i < n; i++)
  54.             for (int j = 0; j < m; j++)
  55.                 c[i][j] = (int)res[i][j];
  56.     }
  57. }