矩阵（矩阵快速幂）

矩阵在计算机数学中有比较重要的内容，它可以优化很多推论，在这里我们将简单介绍一下。

矩阵是什么

由\(n\times m\)个数\(a_{ij}(i=1,2,\dots,n,j=1,2,\dots,m)\)排成的\(m\)行\(n\)列的数表(是一组数)。通用形式：

\[\left[ \begin{matrix} a_1 & a_2 & \cdots\cdots & a_n\\ b_1 & b_2 & \cdots\cdots & b_n\\ \cdots & \cdots & \cdots\cdots & \cdots\\ z_1 & z_2 & \cdots\cdots & z_n \end{matrix} \right] \]

下面了解一些特殊的矩阵：

行（列）矩阵：只有一行（列）的矩阵，又称之为行（列）向量。
同型矩阵：行数和列数都相等的两个矩阵。
零矩阵：所有元素为\(0\)的矩阵，记为\(O\)，不同型的零矩阵是不相等的。
对角矩阵：对角线元素为\(a_1,a_2,\dots,a_n\)，其余元素均为\(0\)的方阵。
单位矩阵：对角线元素为\(1\)，其余元素为\(0\)的方阵。

加法运算

两个矩阵进行一般的加法运算的前提是这两个矩阵为同型矩阵，我们只需要将对应位置的元素相加即可。

\[A=\left[ \begin{matrix} a_1 & a_2 & a_3\\ b_1 & b_2 & b_3\\ c_1 & c_2 & c_3 \end{matrix} \right] ,B=\left[ \begin{matrix} d_1 & d_2 & d_3\\ e_1 & e_2 & e_3\\ f_1 & f_2 & f_3 \end{matrix} \right] ,A+B=\left[ \begin{matrix} a_1+d_1 & a_2+d_2 & a_3+d_3\\ b_1+e_1 & b_2+e_2 & b_3+e_3\\ c_1+f_1 & c_2+f_2 & c_3+f_3 \end{matrix} \right] \]

在矩阵的加法运算中，满足交换律和结合律，也就是\(A+B=B+A,(A+B)+C=A+(B+C)\)。

减法运算

在实数运算中，减法为加法的逆运算，同样的，在矩阵运算中也是如此。

\[A=\left[ \begin{matrix} a_1 & a_2 & a_3\\ b_1 & b_2 & b_3\\ c_1 & c_2 & c_3 \end{matrix} \right] ,B=\left[ \begin{matrix} d_1 & d_2 & d_3\\ e_1 & e_2 & e_3\\ f_1 & f_2 & f_3 \end{matrix} \right] ,A-B=\left[ \begin{matrix} a_1-d_1 & a_2-d_2 & a_3-d_3\\ b_1-e_1 & b_2-e_2 & b_3-e_3\\ c_1-f_1 & c_2-f_2 & c_3-f_3 \end{matrix} \right] \]

数乘

在数乘运算中，我们类比向量来进行理解，在数乘向量运算中，只需要将向量中的每个元素乘上那个数就可以了，数乘矩阵也是如此。

\[A=\left[ \begin{matrix} a_1 & a_2 & a_3\\ b_1 & b_2 & b_3\\ c_1 & c_2 & c_3 \end{matrix} \right] ,3\times A=\left[ \begin{matrix} 3\times a_1 & 3\times a_2 & 3\times a_3\\ 3\times b_1 & 3\times b_2 & 3\times b_3\\ 3\times c_1 & 3\times c_2 & 3\times c_3 \end{matrix} \right] \]

数乘矩阵运算中，满足如下运算律:\((\lambda\times\mu)\times A=\lambda\times(\mu\times A),(\lambda+\mu)\times A=\lambda\times A+\mu\times A,\lambda(A+B)=\lambda\times A+\lambda\times B\)。

乘法运算

了解完矩阵，你们现在我们来看看什么是矩阵乘法？

再次先说明：矩阵相乘前一个矩阵的列数必须等于后一个矩阵的行数\(A_{m\times s}\times B_{s\times n}\)，乘积矩阵的函数为前一个矩阵的行数，列数为后一个矩阵的列数\(C_{m\times n}\)。

现在我们设\(C=A\times B\)（三个都是矩阵），那么就有\(C[i][j]=\sum_{i=1}^s(A[i][k]\times B[k][j])\)。通俗的说，结果矩阵的第\(i\)行第\(j\)列等于矩阵\(A\)第\(i\)行与矩阵\(B\)第\(j\)列分别乘积的和（现在明白为什么矩阵乘法要求\(A\)的行数与\(B\)的列数相同了吧，因为要保证有数相乘，若不相等会导致缺少一些项）

在普通的乘法中，一个数乘\(1\)还是等于它本身，在矩阵乘法中也有这么一个\(“1”\)，它就是单位矩阵。不同于普通乘法中的单位\(1\)，对于不同矩阵他们的单位矩阵大小是不同的对于\(n\times m\)的矩阵，它的单位矩阵大小为\(m\times m\)，对于\(m\times n\)的矩阵，它的单位矩阵大小为\(n\times n\)。也就是说单位矩阵都是正方形的，这是因为只有正方形的矩阵能保证结果和前一个矩阵形状相同，单位矩阵的元素非\(0\)即\(1\)，从左上角到右下角的对角线上元素皆为\(1\)，其他皆为\(0\)。

矩阵快速幂

了解了这么多，我们现在来看矩阵快速幂，矩阵快速幂就是将矩阵和相结合，由于矩阵乘法满足结合律，所以我们只需要把它按照一般的快速幂来写即可。

int n, m, p, k;
struct Mat{
	int arr[10][10];
};

Mat Add(Mat x, Mat y){
	Mat temp;
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			temp.arr[i][j] = x.arr[i][j] + y.arr[i][j];
		}
	}
	return temp;
}

Mat Sub(Mat x, Mat y){
	Mat temp;
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			temp.arr[i][j] = x.arr[i][j] - y.arr[i][j];
		}
	}
	return temp;
}

Mat Mul(Mat x, Mat y){
	Mat temp;
	memset(temp.arr,0,sizeof(temp.arr));
	for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            for (int k = 1; k <= p; k++) {
                temp.arr[i][j] = temp.arr[i][j] + x.arr[i][k] * y.arr[k][j];
            }
        }
    }
	return temp;
}

int main(){
	Mat res, a;
	cin >> n >> k;	
	m = n;
	p = n;
	for(int i = 1; i <= n; i++){
		res.arr[i][i] = 1;
	}
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= n; j++){
			cin >> a.arr[i][j];
		}
	}
	while(k){
		if(k & 1) res = Mul(res,a);
		a = Mul(a,a);
		k >>= 1;
	}
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= n; j++){
			cout << res.arr[i][j] << " ";
		}
		cout << endl;
	}
	return 0;
}

数学矩阵

矩阵（矩阵快速幂）