矩阵（矩阵快速幂）

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

矩阵是什么

由$n\times m$个数$a_{ij}(i=1,2,\dots ,n,j=1,2,\dots ,m)$排成的$m$行$n$列的数表(是一组数)。通用形式：
$$\left[\begin{array}{cccc}{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{array}\right]$$

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

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

加法运算

两个矩阵进行一般的加法运算的前提是这两个矩阵为同型矩阵，我们只需要将对应位置的元素相加即可。
$$A=\left[\begin{array}{ccc}{a}_1& a_2& a_3\\ b_1& b_2& b_3\\ c_1& c_2& c_3\end{array}\right],B=\left[\begin{array}{ccc}{d}_1& d_2& d_3\\ e_1& e_2& e_3\\ f_1& f_2& f_3\end{array}\right],A+B=\left[\begin{array}{ccc}{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{array}\right]$$
在矩阵的加法运算中，满足交换律和结合律，也就是$A+B=B+A,(A+B)+C=A+(B+C)$。

减法运算

在实数运算中，减法为加法的逆运算，同样的，在矩阵运算中也是如此。
$$A=\left[\begin{array}{ccc}{a}_1& a_2& a_3\\ b_1& b_2& b_3\\ c_1& c_2& c_3\end{array}\right],B=\left[\begin{array}{ccc}{d}_1& d_2& d_3\\ e_1& e_2& e_3\\ f_1& f_2& f_3\end{array}\right],A-B=\left[\begin{array}{ccc}{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{array}\right]$$

数乘

在数乘运算中，我们类比向量来进行理解，在数乘向量运算中，只需要将向量中的每个元素乘上那个数就可以了，数乘矩阵也是如此。
$$A=\left[\begin{array}{ccc}{a}_1& a_2& a_3\\ b_1& b_2& b_3\\ c_1& c_2& c_3\end{array}\right],3\times A=\left[\begin{array}{ccc}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{array}\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;
}