矩阵快速幂

#### 阅读本知识点的基本条件 知道什么是矩阵，以及知道如何进行矩阵的乘法。 ### 什么是矩阵快速幂 和快速幂一样，矩阵快速幂是一种可以在O($logn$)的时间复杂度内求出矩阵的$n$次方的算法。 ### 如何写矩阵快速幂 #### 前提1 封装好一个矩阵 ```cpp struct Matrix{ ... friend Matrix operator * (Matrix a, Matrix b) { ... } }; ``` 或者 ```cpp class Matrix{ private : ... public : ... friend Matrix operator * (Matrix a, Matrix b) { ... } }; ``` #### 前提2 找到一个单位1矩阵，也就是说对于任何一个相同大小的矩阵，它乘上单位1矩阵得到的新矩阵都是它自己。 ###### 怎么找一个单位1矩阵呢 你可以自己尝试矩阵构造，这里不多做说明，直接给出结果。 对于一个$x \times x$的矩阵，设它的单位1矩阵为one，那么： ```cpp memset(one, 0, sizeof(one)); for (int i = 1; i <= x; i++) { one[i][i] = 1; } ``` #### 之后就和普通的快速幂没什么区别了 递归代码(求$a^n$) : ```cpp Matrix Kasumi(int n) { if (n == 0) { return one; } Matrix res = Kasumi(n / 2); res = res * res; if (n % 2 == 1) { res *= a; } return res; } ``` 非递归代码：(求$a^n$) ```cpp Matrix Kasumi(int n) { Matrix res = one, base = a; while (n) { if (b % 2 == 1) { ans = ans * base; } base = base * base; b /= 2; } return res; } ``` #### 至于取膜 ```cpp friend Matrix operator % (Matrix a, int mod) { ... } ``` 之后像快速幂一样取膜即可 ### 矩阵快速幂有什么用 矩阵快速幂可以用来求一些数列的第几项的值：比如求斐波那契数列第1000000000位的值。 或者，用矩阵快速幂优化DP，比如说 ： [四重存在](https://www.luogu.org/problemnew/show/T6575)