矩阵快速幂
在讲矩阵快速幂之前,先引入整数快速幂的概念。
整数快速幂
为了引出矩阵快速幂,以及说明快速幂算法的好处,我们可以先求整数的幂。如果现在要算X^8:
则X*X*X*X*X*X*X*X*X
按照寻常思路,一个一个往上边乘,则乘法运算进行7次。
用(X*X)*(X*X)*(X*X)*(X*X)
这种求法,先进行乘法得X^2
,然后对X^2
再执行三次乘法,这样去计算则乘法运算执行4次。已经比七次少。所以为了快速算整数幂,就会考虑这种结合的思想。现在考虑应该怎么分让计算比较快。接下来计算整数快速幂。
例如:X^19
19的二进制为:1 0 0 1 1
由(X^m)*(X^n)=X^(m+n)
则X^19=(X^16)*(X^2)*(X^1)
那么怎么来求解快速幂呢。请看下列代码:
求解X^N的值
int QuickPow(int x,int N)
{
int res = x;
int ans = 1;
while(N)
{
if(N&1)
{
ans = ans * res;
}
res = res*res;
N = N>>1;
}
return ans;
}
矩阵快速幂
看了一个整数的快速幂,现在我们就正式介绍矩阵快速幂算法。假如现在有一个n*n的方阵A。所谓方阵就是行数和列数相等的矩阵,先给出一个数M,让算矩阵A的M次幂,A^M在此只要求计算并不需要去深究这个矩阵到底是什么含义。详细看下边的代码部分
代码部分
struct Matrix
{
int m[maxn][maxn];
}ans,res;
Matrix Mul(Matrix a,Matrix b,int n)
{
Matrix tmp;
for(int i = 1;i <= n;i++)
{
for(int j = 1;j <= n;j++)
{
tmp.m[i][j] = 0;
}
}
for(itn i=1;i <= n;i++)
{
for(int j = 1;j <= n;j++)
{
for(int k = 1;k <= n;k++)
{
tmp.m[i][j] = a.m[i][k]*b.m[k][j];
}
}
}
return tmp;
}
void quickpower(int N,int n)
{
for(int i = 1;i <= n;i++)
{
for(int j = 1;j <= n;j++)
{
if(i == j)
ans.m[i][j] = 1;
else
ans.m[i][j] = 0;
}
}
while(N)
{
if(N&1)
ans = Mul(res,res);
res = Mul(res,res);
N = N>>1;
}
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)