Matrix fast power

نُشر في عُدل في

**1.**矩阵快速幂
1.1 矩阵基础
1.1.1 矩阵
在数学中，矩阵（Matrix）是一个按照长方阵列排列的复数或实数集合 ——-百度百科

​ 1.1.2 矩阵加/减法

​ 矩阵的加法和正常数字的加法很是类似
$$
\left[
\begin{matrix}
1&2 \
3&4
\end{matrix}
\right]
+
\left[
\begin{matrix}
4&3 \
2&1
\end{matrix}
\right]

\left[
\begin{matrix}
1+2&2+3 \
3+2&4+1
\end{matrix}
\right]

\left[
\begin{matrix}
5&5 \
5&5
\end{matrix}
\right]
$$

$$
\left[
\begin{matrix}
5&5 \
5&5
\end{matrix}
\right]

\left[
\begin{matrix}
4&3 \
2&1
\end{matrix}
\right]

\left[
\begin{matrix}
5-4&5-3 \
5-2&5-1
\end{matrix}
\right]

\left[
\begin{matrix}
1&2 \
3&4
\end{matrix}
\right]
$$

​ 1.1.3矩阵数乘

​ 数乘(注意哦,是数乘)是指一个矩阵与一个数相乘,方法就是把矩阵里的每一个元素都乘以该数
$$
3
\times
\left[
\begin{matrix}
4&3 \
2&1
\end{matrix}
\right]

\left[
\begin{matrix}
34&33 \
32&31
\end{matrix}
\right]

\left[
\begin{matrix}
12&9 \
6&3
\end{matrix}
\right]
$$
​ 1.1.4矩阵乘法

​ 矩阵乘法,笔者一开始只看到了它的公式,如下
$$
C_{ij}=\sum_{k=1}^{n}A_{ik}\times B_{kj}
$$
​ 其中A,B能乘的条件是A的列数等于B的行数

​ 如$A=m\times n,B=n\times k$时可乘

​ 但是由于它实在是太抽象(明明是你自己太蠢),笔者花了好长时间还是没有理解,直到我看到了这样一句话

​ 矩阵最初的目的，只是为线性方程组提供一个简写形式

​ 突然茅塞顿开

​ 我们看这样一个式子
$$
\left[
\begin{matrix}
4&3 \
2&1
\end{matrix}
\right]
\times
\left[
\begin{matrix}
2 \
5
\end{matrix}
\right]

\left[
\begin{matrix}
23 \
9
\end{matrix}
\right]
$$
​ 是不是看起来很抽象,无法理解?

​ 但如果我让你解这样一个方程呢
$$
\begin{cases}4x+3y=23 \ 2x+y=9\end{cases}
$$
​ 解为
$$
\begin{cases}x=2 \ y=5\end{cases}
$$
​ 发现什么了么

​ 第一个矩阵可以表示该方程的各系数,第二个可以代表参数,第三个可以看作解

​ 当然,这只是一种比较简洁的记忆方法.其他的理解方法还有很多,留作读者读后思考(划掉

​ 有了这些基本知识我们就可以进行我们的主题了—-矩阵快速幂

​ 1.2矩阵快速幂

​ 矩阵快速幂,即给你一个$n\times n$的矩阵$A$,求$A^n$

​ 为什么一定要是一个正方形矩阵呢

​ 因为只有当两个矩阵行数等于另一个的列数时才能乘,故自乘必须得是一个正方形矩阵

​ 其实矩阵快速幂与普通快速幂没什么区别,只是把$\times$换成了一个函数mat_mul(矩阵乘法)

​ 代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include<iostream>
using namespace std;
const long long mod=1000000007;

struct mat
{
	long long m[105][105];
}a,e,ans;

long long p,n;

mat multi(mat a,mat b)
{
	mat c;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			c.m[i][j]=0;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			for(int k=1;k<=n;k++)
				c.m[i][j]=c.m[i][j]%mod+a.m[i][k]*b.m[k][j]%mod;
	return c;
}

mat ksm(mat x,long long p)
{
	mat res=e;
	while(p)
	{
		if(p&1)
			res=multi(res,a);
		a=multi(a,a);
		p>>=1;
	}
	return res;
}

int main()
{
	cin>>n>>p;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			cin>>a.m[i][j];
	for(int i=1;i<=n;i++)
	{
		e.m[i][i]=1;
	}
	ans=ksm(a,p);
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
			cout<<ans.m[i][j]%mod<<" ";
		cout<<endl;
	}
	return 0;
}