快速幂

设置矩阵A为$m\times p$的矩阵，B为$p \times n$的矩阵，则可有$m \times n$的矩阵c为矩阵A 与B的乘积。

例如

$$C = \left[\begin{array}{a} 1 & 2 & 3\\ 4 & 5 & 6 \end{array} \right] \times \left[\begin{array}{b} 1&4\\ 2&5\\ 3&6\\ \end{array}\right]\\ = \left[\begin{array}{b} 1\times1+2\times2+3\times3&1\times4+2\times5+3\times6\\ 4\times1+5\times2+6\times3&4\times4+5\times5+6\times6 \end{array}\right]\\ =\left[\begin{array}{b} 14&32\\ 32&77\\ \end{array}\right]$$

接下来我们使用矩阵快速幂解决斐波那契问题

我们将斐波那契数列相邻的两项表示为一个矩阵

$$\left[\begin{array}{b} F_n&F_{n-1}\\ \end{array}\right]$$

我们希望通过$\left[\begin{array}{b}F{n-1}&F{n-2}\\end{array}\right]$推出$\left[\begin{array}{b}F{n}&F{n-1}\\end{array}\right]$

尝试构造一个矩阵A使得$\left[\begin{array}{b}F{n-1}&F{n-2}\\end{array}\right]\times=\left[\begin{array}{b}F{n}&F{n-1}\\end{array}\right]$。

$$F_n = F_{n-1}\times1+F_{n-2}+1\\ F_{n-1} = F_{n-1}\times1+F_{n-2}\times0$$

发现$A = \left[\begin{array}{b}1&1\1&0\\end{array}\right]$

那么

$$\left[\begin{array}{b} F_2&F_{1} \end{array}\right]\times \left[\begin{array}{b} 1&1\\1&0 \end{array}\right]^{n-2} =\left[\begin{array}{b} F_n&F_{n-1}\\ \end{array}\right]$$

代码

using ll = long long;
using namespace std;
struct matrix{
	ll c[3][3];
	matrix() { memset(c, 0, sizeof c); }
}F,A;
matrix operator*(matrix& a, matrix& b) {
	matrix t;
	for (int i = 1; i <= 2; i++) {
		for (int j = 1; j <= 2; j++) {
			for (int k; k <= 2; k++) {
				t.c[i][j] = (t.c[i][j] + a.c[i][k] * b.c[k][j]) % mod;
			}
		}
	}
	return t;
}
void quickpow(ll n) {
	F.c[1][1] = F.c[1][2] = 1;
	A.c[1][1] = A.c[1][2] = A.c[2][1] = 1;
	while (n) {
		if (n & 1) F = F * A;
		A = A * A;
		n >>= 1;
	}
}