3
20
2015
0

【口胡向·水】矩阵乘法

Orz 叶队

矩阵乘法,即矩阵相乘→_→,公式:C[i][j] = Sigma(A[i][k] * B[k][j])

写成代码形式就是这样↓

for(int i=1;i<=n;i++)
	for(int j=1;j<=p;j++)
		for(int k=1;k<=m;k++)
			c[i][j]+=a[i][k]*b[k][j];

……嘛,很简单的啦,给道题先→_→

http://codevs.cn/problem/1287/


既然会了矩阵乘法。。那么矩阵乘法有什么用呢(赶脚一点都不实用啊

——它可以用来优化DP

例题→求Fibonacci数列第N项。

先想到递推公式 F(n)=F(n-1)+F(n-2)

虽然这样递推已经很快了,但是矩阵乘法可以做的更快

思考如何从 (n-1,n)转移到(n,n+1)————乘上一个矩阵即可

于是可以发现,乘上一次这个矩阵就是转移一次,乘上两次便是转移两次,所以只要乘上此矩阵的某某次方 便能得到答案~

于是回忆快速幂是怎么样的。。似乎是这样的↓

int quickpow(int m,int n,int k){
	int b=1;
	while(n>0){
		if(n&1)b=(b*m)%k;
		n=n>>1;
		m=(m*m)%k;
	}
	return b;
}

想象一下b,m是矩阵类型,这也是灰常简单的→_→,代码大概是这样的↓↓

struct node{
	long long k[3][3];
}m,tt;

node ju(node a,node b){
	node c;
	memset(c.k,0,sizeof(c.k));
	for(int i=1;i<=2;i++)
		for(int j=1;j<=2;j++){
			c.k[i][j]=0;
			for(int k=1;k<=2;k++){
				c.k[i][j]+=(a.k[i][k]*b.k[k][j])%p;
				c.k[i][j]=c.k[i][j]%p;
			}
		}
	return c;
}

while(n>0){
	if(n&1)tt=ju(tt,m);
	n=n>>1;
	m=ju(m,m);
}

原题在此http://poj.org/problem?id=3070


矩乘还有什么用→_→ ,反正我不知道了,总结一下。。矩乘可以优化转移方案是一样的DP问题……

 

loading...

Category: 算法 | Tags: | Read Count: 2195

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com