矩阵快速幂优化的动态规划

因为最近写矩阵快速幂总是搞反相乘的顺序所以来写一发博客

不过突然写这么简单的东西似乎会被鄙视？

矩阵和矩阵乘法

（没学过矩乘的同学最好不要通过此博客学习，它的目的不在于此）

矩阵是一个由数组成的矩形，特殊地，行数为1的矩阵被称作行向量，列数为1的矩阵被称作列向量。

矩阵A（m*n）和B（n*p）可以进行乘法得到矩阵C（m*p），也就是说当前者的列数等于后者行数的时候。乘法的定义是

cij=∑mk=1Aik∗Bkj

按照定义，可以写出矩阵和矩乘的代码，其中矩乘的效率是O(n*m*p)

struct matrix
{
	int m[maxm][maxm];
	int x,y;
	inline int *operator [](int x)
	{
		return m[x];
	}
	matrix(int x,int y):x(x),y(y)
	{
		memset(m,0,sizeof(m));
	}
	matrix operator *(matrix &b)
	{
		matrix ans(x,b.y);
		for(int i=0;i<x;i++)
			for(int j=0;j<b.y;j++)
				for(int k=0;k<y;k++)
					ans[i][j]+=m[i][k]*b[k][j];//一般的题目都会在此处要求取模，请注意相乘时int溢出
		return ans;
	}
};

矩阵乘法是满足结合律的，也就是说，(A*B)*C=A*(B*C)

矩阵乘法与DP

矩阵快速幂及其优化

matrix operator ^(matrix b,long t)
{
	matrix ans;//此处ans应初始化为单位矩阵
	while(t)
	{
		if(t&1) ans=ans*b;
		b=b*b;
		t>>=1;
	}
	return ans;
}	

void quickmul(matrix *a,matrix *b,matrix *ans)
{
	memset(ans->m,0,sizeof(ans->m));
	for(int i=0;i<a->x;i++)
		for(int j=0;j<b->y;j++)
			for(int k=0;k<a->y;k++)
				ans->m[i][j]+=a->m[i][k]*b->m[k][j];
}
matrix operator ^(matrix in,int t)
{
	matrix tmpbase(in.x,in.y);
	matrix tmp1(in.x),tmp2(in.x);
	matrix *ans=&tmp1,*swapans=&tmp2;
	matrix *b=&in,*swapb=&tmpbase;
	while(t)
	{
		if(t&1)
		{
			quickmul(ans,b,swapans);
			swap(ans,swapans);//交换指针地址，不改变其中的值
		}
		quickmul(b,b,swapb);
		swap(b,swapb);
		t>>=1;
	}
	return *ans;
}

最后

以上就是俊逸小蜜蜂为你收集整理的矩阵快速幂优化的动态规划的全部内容，希望文章能够帮你解决矩阵快速幂优化的动态规划所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。