# 快速冪&矩陣乘法&矩陣快速冪
## 快速冪
### 次方
平常我們在計算$n^m$時
我們式攤開成$n*n*n*n*n*n*...*n$總共$m$個$n$
時間複雜度式$O(m)$
這個時間複雜度不差，但還可以更好

### 快速冪概念
我們把$n^m$換成
的$m$拆成二進位
例如$n^{13}$，13換成二進位是1101，也就是$2^3 * 1 + 2^2 * 1 + 2^1 * 0 + 2^0 * 1$
所以$n^{13}$換成
$\implies n^{2^3 * 1 + 2^2 * 1 + 2^1 * 0 + 2^0 * 1}$
$\implies n^{2^3} * n^{2^2} * n^{2^1 * 0} * n^{2^0}$

計算$n^m$
從$2^0$開始$2^1 \implies 2^2 \implies ... \implies 2^i \implies ... \implies 2^m$
如果二進為中的第$i$個是$1$就乘上去，是$0$就不乘
所以時間複雜度是以$2$為底的$log \implies O(logm)$

### 實作

int qpow(int a, int b){//a^b
    int r = 1;
    int n = b;
    for(;n;n=n >> 1){
        if(n & 1)r = r * a;
        a = a * a;
    }
    return r;
}

## 矩陣乘法
矩陣 $A = \left [ \begin{array}{1} a_{11} & a_{12}\\a_{21} & a_{22}\end{array}\right],\; B = \left [ \begin{array}{1} b_{11} & b_{12}\\b_{21} & b_{22}\end{array}\right]$

則 $AB = \left [ \begin{array}{1} 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]$

### 注意事項
第一個矩陣的列數和第二個矩陣的行數要一樣
算出的矩陣的列是第二個矩陣的列，行是第一個矩陣了行

$\left [ \begin{array}{1} A_{1} \\ A_{2} \\ A_{3} \\\vdots \end{array} \right ] \times \left [ \begin{array} /B_{1}&B_{2}&B_{3}&\dots \end{array} \right ] = \left [ \begin{array}(A_{1}\cdot B_{1})&(A_{1}\cdot B_{2})&(A_{1}\cdot B_{3})&\dots \\(A_{2}\cdot B_{1})&(A_{2}\cdot B_{2})&(A_{2}\cdot B_{3})&\dots \\(A_{3}\cdot B_{1})&(A_{3}\cdot B_{2})&(A_{3}\cdot B_{3})&\dots \\\vdots &\vdots &\vdots &\ddots \end{array} \right ]$

### 程式實作

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

也可以用struct建矩陣，在struct裡用operator*
### 練習題
[題目](http://203.64.191.163/ShowProblem?problemid=a871)
這題不用快速冪就可以過了

## 矩陣快速冪
有可矩陣乘法的code後，矩陣快速冪就和一般的快速冪差不多了
記得要回傳的矩陣初始化時要初始化成單位矩陣

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

## 延伸學習
矩陣快速冪還可以用在DP優化上喔
[DP優化](/dvHGezXpRu-SLAj7McPc4A)