矩阵快速幂 算法原理与模板

一.前导知识(线性代数)

1.矩阵乘法

※运算公式
[ a 11 a 12 . . . a 1 n a 21 a 22 . . . a 2 n . . . . . . . . . . . . a n 1 a n 2 . . . a n n ]   ⋅   [ b 11 b 12 . . . b 1 n b 21 b 22 . . . b 2 n . . . . . . . . . . . . b n 1 b n 2 . . . b n n ]   =   [ c 11 c 12 . . . c 1 n c 21 c 22 . . . c 2 n . . . . . . . . . . . . c n 1 c n 2 . . . c n n ] ⟨ c i j = ∑ k = 1 n a i k ∗ b k j ⟩ \begin{bmatrix} a_{11}&a_{12}&{...}& a_{1n}\\ a_{21}&a_{22}&{...}& a_{2n}\\ {...}&{...}&{...}&{...}\\ a_{n1}&a_{n2}&{...}& a_{nn}\\ \end{bmatrix} \ \cdot \ \begin{bmatrix} b_{11}&b_{12}&{...}& b_{1n}\\ b_{21}&b_{22}&{...}& b_{2n}\\ {...}&{...}&{...}&{...}\\ b_{n1}&b_{n2}&{...}& b_{nn}\\ \end{bmatrix} \ = \ \begin{bmatrix} c_{11}&c_{12}&{...}& c_{1n}\\ c_{21}&c_{22}&{...}& c_{2n}\\ {...}&{...}&{...}&{...}\\ c_{n1}&c_{n2}&{...}& c_{nn}\\ \end{bmatrix}\\ \langle c_{ij} = \sum^{n}_{k =1}a_{ik}*b_{kj} \rangle ⎣⎢⎢⎡​a11​a21​...an1​​a12​a22​...an2​​............​a1n​a2n​...ann​​⎦⎥⎥⎤​ ⋅ ⎣⎢⎢⎡​b11​b21​...bn1​​b12​b22​...bn2​​............​b1n​b2n​...bnn​​⎦⎥⎥⎤​ = ⎣⎢⎢⎡​c11​c21​...cn1​​c12​c22​...cn2​​............​c1n​c2n​...cnn​​⎦⎥⎥⎤​⟨cij​=k=1∑n​aik​∗bkj​⟩
※代码表示

const int N = 100;
int c[N][N];
void matrix_multi(int a[][N], int b[][N], int n){
    memset(c, 0, sizeof(c));
    for(register int i = 1; i = 1;
  }
  return res;
}

模意义下取幂

long long binpow(long long a, long long b, long long m) {
  a %= m;
  long long res = 1;
  while (b > 0) {
    if (b & 1) res = res * a % m;
    a = a * a % m;
    b >>= 1;
  }
  return res;
}

注意：根据费马小定理，如果 m m m 是一个质数，我们可以计算 x n   m o d   ( m − 1 ) x^{n\bmod (m-1)} xnmod(m−1) 来加速算法过程。

二、矩阵快速幂

1.实例导入

给定整数 n n n，计算斐波那契数列的第 n n n项 F n F_n Fn​。

首先，观察斐波那契数列的特征：递推公式： F n = F n − 1 + F n − 2 F_n = F_{n-1} + F_{n-2} Fn​=Fn−1​+Fn−2​

我们不难发现： F n F_n Fn​与 F n − 1 F_{n- 1} Fn−1​和 F n − 1 F_{n - 1} Fn−1​与 F n − 2 F_{n -2} Fn−2​之间的关系可以用矩阵的乘法关系进行描述：
[ F n − 1 F n ]   =   [ F n − 2 F n − 1 ]   ⋅   [ 0 1 1 1 ] \begin{bmatrix} F_{n - 1}&F_{n}\\ \end{bmatrix} \ = \ \begin{bmatrix} F{n - 2}&F_{n - 1} \end{bmatrix} \ \cdot \ \begin{bmatrix} 0&1\\ 1&1\\ \end{bmatrix} [Fn−1​​Fn​​] = [Fn−2​Fn−1​​] ⋅ [01​11​]
不妨设 P = [ 0 1 1 1 ] P = \begin{bmatrix}0 & 1 \cr 1 & 1 \cr\end{bmatrix} P=[01​11​]，改写递推公式，可得：
[ F n F n + 1 ] = [ F 0 F 1 ] ⋅ P n \begin{bmatrix}F_n & F_{n+1} \cr\end{bmatrix} = \begin{bmatrix}F_0 & F_1 \cr\end{bmatrix} \cdot P^n [Fn​​Fn+1​​]=[F0​​F1​​]⋅Pn
于是我们可以用矩阵乘法在 Θ ( log ⁡ n ) \Theta(\log n) Θ(logn) 的时间内计算斐波那契数列。

实际上，对于斐波那契数列，我们可以根据上述原理继续优化：即快速倍增法。这里不深入讨论。

根据上述题目，我们不难看出，对于具有类似特征的问题，我们可以根据题目构造相应的矩阵达到优化计算的目的。

2.矩阵快速幂模板

const int N = 10;
int tmp[N][N];

void multi(int a[][N], int b[][N], int n){
    memset(tmp, 0, sizeof tmp);
    for (int i = 0; i