矩阵快速幂

矩阵快速幂矩阵快速幂,就是矩阵乘法和快速幂的结合,所以在讲矩阵快速幂之前,先讲讲矩阵乘法和快速幂。矩阵矩阵的定义什么是矩阵?由$m\timesn$个数$a_{i,j}(i=1,2,\cdots,m;j=1,2,\cdots,n)$排成的一个$m$行$n$列的数表$$\begin{m

大家好,欢迎来到IT知识分享网。矩阵快速幂"

矩阵快速幂,就是矩阵乘法和快速幂的结合,所以在讲矩阵快速幂之前,先讲讲矩阵乘法和快速幂。

矩阵

矩阵的定义

什么是矩阵?由 \(m \times n\) 个数 \(a_{i,j}(i=1,2,\cdots,m;j=1,2,\cdots,n)\) 排成的一个 \(m\)\(n\) 列的数表

\[\begin{matrix} a_{1,1} & a_{1,2} & \cdots & a_{1,n} \\ a_{2,1} & a_{2,2} & \cdots & a_{2,n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{m,1} & a_{m,2} & \cdots & a_{m,n} \end{matrix}\]

被称为 \(m\)\(n\) 列矩阵,简称 \(m \times n\) 矩阵。为了表示这是个整体总是加一个括弧,并用大写字母表示他,计做:

\[A = \left[\begin{matrix} a_{1,1} & a_{1,2} & \cdots & a_{1,n} \\ a_{2,1} & a_{2,2} & \cdots & a_{2,n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{m,1} & a_{m,2} & \cdots & a_{m,n} \end{matrix}\right]\]

这个矩阵中的\(m \times n\)个数被称为矩阵\(A\)的元素,简称元。矩阵\(A\)也可被计做\(A_{m \times n}\)

行矩阵(行向量): 只有一行的矩阵。
列矩阵(列向量): 只有一列的矩阵。
同型矩阵: 两个矩阵\(A\)\(B\)的行数和列数都相等
单位矩阵: 在矩阵乘法中起着很大的作用,相当于乘法中的\(1\),她是个方阵(即行数和列数相同的矩阵),左上角到右下角的对角线(被称为主对角线)上的元素都是\(1\),除此之外都是\(0\)。如下就是一个\(4 \times 4\)的单位矩阵:

\[\left[\begin{matrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{matrix}\right]\]

矩阵加法

我们定义两个m \(\times n\)的矩阵\(A\)\(B\)相加为:

\[A+B = \left[\begin{matrix} a_{1,1}+b_{1,1} & a_{1,2}+b_{1,2} & \cdots & a_{1,n}+b_{1,n} \\ a_{2,1}+b_{2,1} & a_{2,2}+b_{2,2} & \cdots & a_{2,n}+b_{2,n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{m,1}+b_{m,1} & a_{m,2}+b_{m,2} & \cdots & a_{m,n}+b_{m,n} \end{matrix}\right]\]

注意:

  • 矩阵加法满足交换律和结合律
  • 只有两个同型矩阵才可以做加法

矩阵乘法

我们定义两个矩阵 \(A_{m \times s}\)\(B_{s \times n}\) 相乘得到一个矩阵 \(C_{m,n}\),并且

\[c_{i,j} = a_{i,1}b_{1,j}+a_{i,2}b_{2,j} \cdots +a_{i,s}b_{s,j}=\sum^{s}_{k=1}a_{i,k}b_{k,j} \]

并将此计做 \(C=AB\)
注意: 矩阵乘法不满足交换律,但满足结合律和分配律。
\(\tiny{\text{这里没放图是因为放了也看不懂(逃}}\)
如果还不理解的话可以看这里
用代码写出来就是下面这个亚子:

struct matrix
{
	int n,m;//n是行数,m是列数
	ll e[105][105];
}a;
matrix mul(matrix a,matrix b)
{
	matrix ans;
	ans.n=a.n;
	ans.m=b.m;
	for(int i=1;i<=ans.n;i++)
		for(int j=1;j<=ans.m;j++)
			ans.e[i][j]=0;//初始化
	for(int i=1;i<=a.n;i++)
		for(int j=1;j<=b.m;j++)
			for(int k=1;k<=a.m;k++)
				ans.e[i][j]=(ans.e[i][j]+(a.e[i][k]*b.e[k][j])%mod)%mod;//矩阵乘法结果可能很大,所以要取模
	return ans;
}

快速幂

一般我们求 \(x^y\) 的方法是一个个乘过去,但这种方法太慢了。我们需要一种新的,快速的方法来求,而这种方法就是快速幂。这里我们举例来理解,就比如求 \(3^{5}\),用 \(ans\) 记录答案。\(5\) 转成二进制就是 \({(101)}_2\),那么我们从右往左开始枚举,首先,有个1,那么我们就记录 \(ans=ans \times 3=1 \times 3=3\),然后让 \(3\) 变成自己的平方,也就是 \(3^2=9\) ,然后接下来是个 \(0\),那就不用乘,然后再让 \(9\) 变成自己的平方 \(81\),然后又是个 \(1\),所以 \(ans=ans \times 81=3 \times 81=243\)。最后,得到 \(3^5 = 243\)。手算一下可以发现这是对的。当然 \(x^y\) 很可能是个很大的数,所以一般都会取模。
代码实现长这个亚子:

long long power(long a,long b,long c)
{
	long long ans=1;
	while(b)//没有枚举完
	{
		if(b&1) ans=(ans*a)%c;//这一位是否是1
		a=(a*a)%c;
		b>>=1;//走到下一位
	}
	return ans%c;
}

矩阵快速幂

讲完了上面这些,那矩阵快速幂就很好理解了!就是把运算改成矩阵运算。
首先,\(ans\) 和返回值都应该是一个矩阵;然后,\(ans\) 应该初始化为单位矩阵,原因上面已经讲了;(1.1 矩阵的定义)再然后,里面的乘法应该改成矩阵乘法。最后提醒一句,矩阵快速幂必须是个方阵,否则要两个同型矩阵(自己乘自己,当然是同型矩阵啦~)可以实现矩阵乘法是不可能的。
代码实现:

struct matrix
{
	int n,m;
	ll e[105][105];
}a;
matrix mul(matrix a,matrix b)
{
	matrix ans;
	ans.n=a.n;
	ans.m=b.m;
	for(int i=1;i<=ans.n;i++)
		for(int j=1;j<=ans.m;j++)
			ans.e[i][j]=0;
	for(int i=1;i<=a.n;i++)
		for(int j=1;j<=b.m;j++)
			for(int k=1;k<=a.m;k++)
				ans.e[i][j]=(ans.e[i][j]+(a.e[i][k]*b.e[k][j])%mod)%mod;//快速幂的取模就在这里了!
	return ans;
}//代码和上面的区别
matrix power(matrix a,ll b)
{
	matrix ans;
	ans.n=a.n;
	ans.m=a.m;
	for(int i=1;i<=ans.n;i++)
		for(int j=1;j<=ans.m;j++)
			if(i==j) ans.e[i][j]=1;
			else ans.e[i][j]=0;//初始化为单元矩阵
	while(b)
	{
		if(b&1) ans=mul(ans,a);//要把乘换成矩阵乘法哦!
		a=mul(a,a);//这里也一样呢
		b>>=1;
	}//快速幂板子
	return ans;
}

实际应用

先挂上神仙同学的矩阵加速友链。

矩阵快速幂可以应用到很多递推题上。
先放出一道例题:洛谷P1962 斐波那契数列

这题看到 \(n < 2^{63}\) 就知道,直接递推肯定不行,我们就要用矩阵快速幂来加加速。
我们知道,这题是由初始的两个数递推得来的,那么我们有没有什么办法让他用更快的速度来递推呢?
当然是用矩阵啦~
由于递推 \(F_n\) 需要用到 \(F_{n-1},F_{n-2}\) 两个项,所以我们就构建有两个项的初始矩阵:

\[A=\left[\begin{matrix} F_{n-1} & F_{n-2} \end{matrix}\right]\]

然后,显而易见地,目标矩阵长这个样子:

\[B=\left[\begin{matrix} F_n & F_{n-1} \end{matrix}\right]\]

然后,就有了一个递推式子:

\[AC=B \]

但是我们不知道这个 \(C\) 是什么呀。
没关系,我们来把上面的式子拆开来:

\[AC=\left[\begin{matrix} f_{n-1} \times c_{1,1}+f_{n-2} \times c_{2,1} & f_{n-1} \times c_{2,1}+f_{n-2} \times c_{2,2} \end{matrix}\right]\]

为了让结果等于 \(B\),必须要让

  • \(f_{n-1} \times c_{1,1}+f_{n-2} \times c_{2,1} = f_{n-1}+f_{n-2}\),所以 \(c_{1,1},c_{2,1}\) 都应该等于 \(1\)
  • \(f_{n-1} \times c_{1,2}+f_{n-2} \times c_{2,2} = f_{n-1}\),所以 \(c_{1,2}=1,c_{2,2}=0\)

于是就得到了

\[C=\left[\begin{matrix} 1 & 1 \\ 1 & 0 \end{matrix}\right]\]

但是,这样不还是 \(O(n)\) 递推吗?
观察一下,可以发现每次乘的是同一个矩阵,而原来的递推每次的项是不一样的。
这样有什么好处呢?我们可以先让所有的 \(C\) 都乘起来,再乘 \(A\) 就行了。
能这样做,还是因为矩阵乘法满足结合律
那么要乘几个 \(C\) 呢?是 \(n-2\) 次。为什么呢?因为初始矩阵中已经有了两项:\(F_1\)\(F_2\)

最终代码如下:

#include<cstdio>
#define ll long long
#define mod 1000000007
using namespace std;
ll n;
struct matrix
{
	int n,m;
	ll e[105][105];
}a,b;
matrix mul(matrix a,matrix b)
{
	matrix ans;
	ans.n=a.n;
	ans.m=b.m;
	for(int i=1;i<=ans.n;i++)
		for(int j=1;j<=ans.m;j++)
			ans.e[i][j]=0;
	for(int i=1;i<=a.n;i++)
		for(int j=1;j<=b.m;j++)
			for(int k=1;k<=a.m;k++)
				ans.e[i][j]=(ans.e[i][j]+(a.e[i][k]*b.e[k][j])%mod)%mod;
	return ans;
}
matrix power(matrix a,ll b)
{
	matrix ans;
	ans.n=a.n;
	ans.m=a.m;
	for(int i=1;i<=ans.n;i++)
		for(int j=1;j<=ans.m;j++)
			if(i==j) ans.e[i][j]=1;
			else ans.e[i][j]=0;
	while(b)
	{
		if(b&1) ans=mul(ans,a);
		a=mul(a,a);
		b>>=1;
	}
	return ans;
}
int main()
{
	scanf("%lld",&n);
	if(n<=2)
	{
		printf("1");
		return 0;
	}
	a.n=2,a.m=2;
	a.e[1][1]=a.e[1][2]=a.e[2][1]=1;
	a=power(a,n-2);
	b.n=1,b.m=2;
	b.e[1][1]=b.e[1][2]=1;
	printf("%lld",mul(b,a).e[1][1]);
	return 0;
}

免责声明:本站所有文章内容,图片,视频等均是来源于用户投稿和互联网及文摘转载整编而成,不代表本站观点,不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益,请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权,请联系删除,如若转载,请注明出处:https://yundeesoft.com/30983.html

(0)

相关推荐

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

关注微信