---
tags: 進階班
---
# 快速冪 & 矩陣乘法
## 用途
在做次方乘法的時候,可以讓複雜度從 $O(N)\Rightarrow O(lgN)$!
且快速冪可以用在一般整數乘法、矩陣乘法。
## 作法
### 整數快速冪
對於計算 $n^m$,可以先將 $m$ 轉換成 $2$ 進位,然後依指數律次方相加的特性算出 $n^m$。
例:計算 $3^{29}$ 時,可以將上述式子改為 $3^{16}\times 3^8\times 3^4\times 3^1$,如此即可以只使用 $5$ 次運算就得到 $3^{29}$ 而不是 $29$ 次。
為甚麼是 $5$ 次呢?
:::spoiler `可以先想想`
因為要算出 $3^{16}$ 必須要算出 $3^1, 3^2,3^4,3^8,3^{16}$,共 $5$ 次運算。
:::
\
然後因為次方的答案上升速度過快,因此通常題目都會要求 $mod\;prime$
會選擇質數的原因是因為還有「模逆元」這個應用。
那麼對於正常的整數快速冪部分直接上 `code`
```cpp=
#include<bits/stdc++.h>
using namespace std;
#define ll long long
constexpr int mod = 1e9 + 7;
ll fpow(ll i, int j) {
ll ret = 1, tmp = i;
for (; j; j >>= 1, tmp = tmp * tmp % mod)
if (j & 1) ret = ret * tmp % mod;
return ret;
}
int main() {
int m, n;
cin >> m >> n;
cout << fpow(m, n);
}
```
---
### 矩陣快速冪
在了解矩陣快速冪之前,首先應該先知道矩陣乘法。
對於兩個矩陣 $A = \left [ \begin{array}{cc} a_{11} & a_{12}\\a_{21} & a_{22}\end{array}\right],\; B = \left [ \begin{array}{cc} b_{11} & b_{12}\\b_{21} & b_{22}\end{array}\right]$
則 $AB = \left [ \begin{array}{cc} a_{11}\times b_{11} + a_{12}\times b_{21} & a_{11}\times b_{12} + a_{12}\times b_{22}\\a_{21}\times b_{11} + a_{22}\times b_{21} & a_{21}\times b_{12} + a_{22}\times b_{22}\end{array}\right]$
簡單來說,矩陣乘法有 $2$ 個地方要注意:
1. $A$ 的長寬為 $p\times q$,$B$ 的長寬為 $q\times r$,則 $AB$ 才可相乘,且 $AB$ 的長寬為 $p\times r$
2. $A$ 矩陣的遍歷方法為由左到右,由上到下;$B$ 矩陣的遍歷方法則是由上到下,由左到右。
矩陣乘法 `code`:
```cpp=
vector<vector<ll>> mat(vector<vector<ll>> &x, vector<vector<ll>> &y) {
vector<vector<ll>> ret(p, vector<ll> (r, 0));
for (int i = 0; i < p; i++)
for (int j = 0; j < r; j++)
for (int k = 0; k < q; k++)
ret[i][j] = (ret[i][j] + x[i][k] * y[k][j]) % mod;
return ret;
}
```
那麼矩陣快速冪就會跟整數快速冪長很像了:
```cpp=9
vector<vector<ll>> mpow(vector<vector<ll>> x, ll y) {
vector<vector<ll>> ret = I, tmp = x;
for (; y; y >>= 1, tmp = mat(tmp, tmp))
if (y & 1) ret = mat(ret, tmp);
return ret;
}
```
當然,想把 `mat()` 換成 `operator*` 也可以 :poop:
上面矩陣快速冪有一個 `I`,它代表單位矩陣,相當於正常乘法中的 $1$,即 $IA = AI = A$
$I = \left [\begin{array}{cc} 1 & 0\\ 0 & 1\end{array}\right]$ (矩陣大小為 $2\times 2$ 時)
## 應用
### 模逆元
在整數乘法時,可以對乘法做「模運算」,即 `n * (m % mod) = (n * m) % mod`
但除法時,`n / (m % mod) = (n / m) % mod` **並不成立**
因此在做除法運算又需要進行模運算時,要怎麼做呢?
對於一質數 $p$ 且 $a < p$,則 $a^{p - 1} \;mod\; p \equiv 1$ (費馬小定理)
$\Rightarrow a\times a^{p - 2}\; mod\; p \equiv 1$
$\Rightarrow a^{p - 2}\; mod\; p \equiv \cfrac{1}{a}$
好像不知不覺就把除法變乘法了?
而所謂的 $a ^{p - 2}$ 就是模逆元,它可以充當模運算時的除法運算數。
通常 $p$ 會很大,所以使用整數快速冪較佳。
也因此題目通常都不會太為難,大部分都會對質數取模,常見取模數有
$1000000007\; (10^9 + 7),\;998244353$ 等
---
### 遞迴數列 $O(N)\rightarrow O(lgN)$
舉常見的費氏數列為例:
$f_n=\begin{cases}\
1\quad\quad\quad\quad\quad\; if\quad n = 0 \;or\; n = 1 \\
f_{n - 1} + f_{n - 2}\quad else
\end{cases}$
可以轉換為:
$f_n = \left [ \begin{array}{cc} 1&0\end{array}\right]{\left [ \begin{array}{cc} 1 & 1\\1 & 0\end{array}\right]}^n$
答案取左矩陣上方的數字即可。
| | |$1$ | $1$|
|-|-|:-:|:-:|
| | |$1$| $0$|
|$a_{n - 1}$ |$a_{n - 2}$ |$a_{n - 1} + a_{n - 2}$ | $a_{n - 1}$ |
基本上,只要是遞迴數列都可以轉換成矩陣表示,而轉換方法有很多種,就請各位熟悉後自己去試試看吧!