矩阵乘法

具有结合律，不具有交换律。
一般结合快速幂使用。

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

思路：
构造矩阵

F[n] = [f(n), f(n + 1), s(n)]
F[n + 1] = [f(n + 1), f(n + 2), s(n + 1)]
F[n + 1] = F[n] * [[0, 1, 0], [1, 1, 1], [0, 0, 1]];
A = [[0, 1, 0], [1, 1, 1], [0, 0, 1]]

import java.util.*;
public class Main {
    static int n, m;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        long[][] A = {{0, 1, 0},  {1, 1, 1}, {0, 0, 1}};
        long[][] F = {{1, 1, 1}};
        A = qmi(A, n - 1);
        F = matrixMul(F, A);
        System.out.println(F[0][2]);
    }
    static long[][] qmi(long[][] b, int c) {
        int len = b.length;
        long[][] res = new long[len][len];
        for (int i = 0; i < len; i++)
            res[i][i] = 1;
        while (c > 0) {
            if ((c & 1) == 1)
                res = matrixMul(res, b);
            c >>= 1;
            b = matrixMul(b, b);
        }
        return res;
    }
    static long[][] matrixMul(long[][] a, long[][] b) {
        int row = a.length, col = b[0].length, t = b.length;
        long[][] res = new long[row][col];
        for (int k = 0; k < t; k++) {
            for (int i = 0; i < row; i++) {
                for (int j = 0; j < col; j++) {
                    res[i][j] = (res[i][j] + (a[i][k] * b[k][j])) % m;
                }
            }
        }
        return res;
    }
}

AcWing 1304. 佳佳的斐波那契

佳佳对数学，尤其对数列十分感兴趣。
在研究完 Fibonacci 数列后，他创造出许多稀奇古怪的数列。
例如用 S(n) 表示 Fibonacci 前 nn 项和 modmmodm 的值，即 S(n)=(F1+F2+…+Fn)modm，其中 F1=F2=1,Fi=Fi−1+Fi−2。
可这对佳佳来说还是小菜一碟。
终于，她找到了一个自己解决不了的问题。
用 T(n)=(F1+2F2+3F3+…+nFn)modm 表示 Fibonacci 数列前 n 项变形后的和 modm 的值。
现在佳佳告诉你了一个 n 和 m，请求出 T(n) 的值。
输入格式
共一行，包含两个整数 n 和 m。
输出格式
共一行，输出 T(n) 的值。
数据范围
1≤n,m≤231−1
输入样例：
5 5
输出样例：
1
样例解释
T(5)=(1+2×1+3×2+4×3+5×5)mod5=1

思路：
递推公式 + 矩阵乘法+ 快速幂

// 如何表示 T(n)
T(n) = f(1) + 2f(2) + ... + nf(n)
nS(n) - T(n) = (n - 1)f(1) + (n - 2)f(2) + ... + f(n - 1)
(n + 1)S(n + 1) - T(n + 1) = n(1) + (n - 1)f(2) + ... + 2f(n - 1) + f(n)
令P(n) = nS(n) - T(n)
p(n + 1) = P(n) + S(n)
故可设
F(n) = [f(n) f(n+1) S(n) P(n)]
F(n + 1) = [f(n+1) f(n+2) S(n+1) P(n+1)] = F(n) * 
[
    [0 1 0 0]
  [1 1 1 0]
  [0 0 1 1]
  [0 0 0 1]
]

import java.util.*;
public class Main {
    static int n, m;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        long[][] A = {
            {0, 1, 0, 0},
            {1, 1, 1, 0},
            {0, 0, 1, 1},
            {0, 0, 0, 1}
        };
        long[][] F = {
            {1, 1, 1, 0}
        };
        A = qmi(A, n - 1);
        F = matrixMul(F, A);
        System.out.println(((n * F[0][2] - F[0][3]) % m + m) % m);
    }
    static long[][] qmi(long[][] a, int b) {
        int len = a.length;
        long[][] res = new long[len][len];
        for (int i = 0; i < len; i++)
            res[i][i] = 1;
        while (b > 0) {
            if ((b & 1) == 1)
                res = matrixMul(res, a);
            b >>= 1;
            a = matrixMul(a, a);
        }
        return res;
    }
    static long[][] matrixMul(long[][] a, long[][] b) {
        int row = a.length, col = b[0].length, t = a[0].length;
        long[][] res = new long[row][col];
        for (int k = 0; k < t; k++) {
            for (int i = 0; i < row; i++) {
                for (int j = 0; j < col; j++) {
                    res[i][j] = (res[i][j] + a[i][k] * b[k][j]) % m;
                }
            }
        }
        return res;
    }
}