--- 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}$ | 基本上,只要是遞迴數列都可以轉換成矩陣表示,而轉換方法有很多種,就請各位熟悉後自己去試試看吧!