标签：begin end mat int 矩阵 bmatrix 相关

矩阵相关运算

结构体定义

typedef long long ll;
const int N = 110;
int n, mod;

struct Mat {
	int n, m; //矩阵的行和列
    int a[N][N];
	void zero() { //0矩阵 
		memset(a, 0, sizeof(a));
	}
	void one() { //n*n的单位矩阵 
		zero();
		for (int i = 1; i <= n; i++) a[i][i] = 1;
	}
	void resize(int x, int y) { //设置矩阵大小 
		n = x; m = y;
	}
	//矩阵加，第二个const表示不能修改成员变量的值，对数据起到保护作用，下同
	Mat operator +(const Mat &A) const {
		Mat res;
		res.resize(n, A.m);
		
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				res.a[i][j] = (a[i][j] + A.a[i][j]) % mod; 
			}
		}
		return res;
	}
	
	//矩阵减 
	Mat operator -(const Mat &A) const {
		Mat res;
		res.resize(n, A.m);
		
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				res.a[i][j] = (a[i][j] - A.a[i][j]) % mod; 
			}
		}
		return res;
	}
	
	//矩阵乘 
	Mat operator *(const Mat &A) const {
		Mat res;
		res.resize(n, A.m);
		res.zero();
		
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= A.m; j++) {
				for (int k = 1; k <= m; k++) {
					res.a[i][j] = ((ll)a[i][k] * A.a[k][j] + res.a[i][j]) % mod;
				}
			}
		}
		return res;
	}
	//输出矩阵 
	void ouput() {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				printf("%d ", a[i][j]);
			}
			putchar('\n');
		}
	}
};

矩阵快速幂

可以利用上面定义好的结构，方便写出矩阵快速幂的形式。

例 1：计算斐波那契数

【问题描述】

计算斐波那契数列的第 \(n\) 项 \(F_n\)（\(1\le n\le 2\times 10^9\)）。

【分析】

根据斐波那契数列的递推式 \(F_n = F_{n-1} + F_{n-2}\)，我们可以构建一个 \(2\times 2\) 的矩阵来表示从 \(F_n,F_{n+1}\) 到 \(F_{n+1},F_{n+2}\) 的变换。于是在计算这个矩阵的 \(n\) 次幂的时侯，我们使用快速幂的思想，可以在 \(\Theta(\log n)\) 的时间内计算出结果。

根据斐波那契数列 递推公式的矩阵形式：

\[\begin{bmatrix} F_{n-1} & F_{n-2} \end{bmatrix} \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} = \begin{bmatrix} F_n & F_{n-1} \end{bmatrix} \]

我们定义初始矩阵

\[\begin{bmatrix}F_2 & F_1\end{bmatrix} = \begin{bmatrix}1 & 1\end{bmatrix}, \text{base} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} \]

那么，

\[\text{ans}=\begin{bmatrix}F_2 & F_1\end{bmatrix}\times\text{base}^{n-2} \]

则 \(F_n\) 就等于 \(ans\) 矩阵的第一行第一列元素。

为什么要乘上 \(\text{base}\) 矩阵的 \(n-2\) 次方而不是 \(n\) 次方呢？因为 \(F_1, F_2\) 是不需要进行矩阵乘法就能求的。也就是说，如果只进行一次乘法，就已经求出 \(F_3\) 了，手算一下就能理解了。

【示例代码】

//矩阵快速幂 
Mat qpow(Mat A, int b) {
	Mat res;
	res.resize(2, 2);
	res.one();
	while (b) {
		if (b & 1) {
			res = res * A;
		}
		A = A * A;
		b >>= 1;
	}
	return res;
}

int main() {
	Mat mat;
	scanf("%d%d", &n, &mod);
	//初始化矩阵 
	mat.resize(2, 2);
	mat.a[1][1] = mat.a[1][2] = mat.a[2][1] = 1;
	mat.a[2][2] = 0;
	
	mat = qpow(mat, n-2);
	int ans = (mat.a[1][1] + mat.a[2][1]) % mod;
	printf("%d\n", ans);
	return 0;
}

标签：begin,end,mat,int,矩阵,bmatrix,相关
From： https://www.cnblogs.com/kuangbiaopilihu/p/17988622