---
# System prepended metadata

title: 快速冪 & 矩陣乘法
tags: [進階班]

---

---
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}$ |



基本上，只要是遞迴數列都可以轉換成矩陣表示，而轉換方法有很多種，就請各位熟悉後自己去試試看吧！