1.算法描述
由于矩阵乘法具有结合律,因此A^4 = A * A * A * A = (A*A) * (A*A) = A^2 * A^2。我们可以得到这样的结论:当n为偶数时,A^n = A^(n/2) * A^(n/2);当n为奇数时,A^n = A^(n/2) * A^(n/2) * A (其中n/2取整)。这就告诉我们,计算A^n也可以使用二分快速求幂的方法。例如,为了算出A^25的值,我们只需要递归地计算出A^12、A^6、A^3的值即可[1]。
在运算过程中,为了避免高精度运算,可采用取模(具体原因参看[1, 2])。
2.Referrence
[1] Matrix67, 十个利用矩阵乘法解决的经典题目
[2] Matrix67, 同余运算及其基本性质
[3]shiwei408,矩阵快速幂 poj3070 3233
3735 3150
3.问题
3.1 POJ 3070
求Fibonacci数Fn=Fn−
1+Fn− 2forn≥
2 对10000取余。
题目已经给出了优化解决方案:对矩阵求n次幂,取n次幂的[0][1]元素,即为Fn
。
源代码:
3070 |
Accepted |
116K |
0MS |
C |
1178B |
2013-08-25 22:27:23 |
#include "stdio.h"
#include "string.h"
#define Mod 10000
typedef struct
{
int arr[2][2];
}Matrix;
/*multiply the two matrices*/
Matrix mMulti(Matrix a, Matrix b)
{
int i, j, k;
Matrix d;
memset(d.arr,0,sizeof(d.arr));
for(i=0;i<2;i++)
for(j=0;j<2;j++)
{
for(k=0;k<2;k++)
d.arr[i][j]+=a.arr[i][k]*b.arr[k][j];
d.arr[i][j]%=Mod;
}
return d;
}
/*the k-th power of matrix a*/
Matrix mPow(Matrix a, int k)
{
Matrix modd,meven;
modd.arr[0][0]=1; modd.arr[0][1]=0; //matrix modd is initialized to be a unit matrix
modd.arr[1][0]=0; modd.arr[1][1]=1;
meven=a; //matrix meven is initialized
if(k==0)
return modd;
else
{
while(k!=1)
{
if(k&1)
{
k--;
modd=mMulti(modd,meven);
}
else
{
k/=2;
meven=mMulti(meven,meven);
}
}
return mMulti(modd,meven);
}
}
int main()
{
int n;
Matrix fibonacci, goal;
fibonacci.arr[0][0]=1; fibonacci.arr[0][1]=1;
fibonacci.arr[1][0]=1; fibonacci.arr[1][1]=0;
while(scanf("%d",&n)&&n!=-1)
{
goal=mPow(fibonacci,n);
printf("%d\n",goal.arr[0][1]%Mod);
}
return 0;
}
3.2 POJ 3233
求n×n方阵A+A2+A3+
… +Ak
在Discuss中给出了优化解决思路:
| A+A^2+A^3+……A^k | |A A| (k-1)次方 | A |
| | = | | | |
| E | |0 E| | E |
一次提交就AC了,不过代码还可以继续优化。
源代码:
3233 |
Accepted |
284K |
719MS |
C |
1451B |
2013-08-27 23:04:22 |
#include "stdio.h"
#include "string.h"
#define MAX 60
typedef struct
{
int arr[MAX][MAX];
}Matrix;
int n,m;
/*multiplication*/
Matrix mMulti(Matrix a, Matrix b)
{
int i, j, k;
Matrix d;
memset(d.arr,0,sizeof(d.arr));
for(i=0;i<2*n;i++)
for(j=0;j<2*n;j++)
for(k=0;k<2*n;k++)
d.arr[i][j]=(d.arr[i][j]+a.arr[i][k]*b.arr[k][j])%m;
return d;
}
/*the k-th power of matrix a*/
Matrix mPow(Matrix a,int k)
{
int i;
Matrix modd,meven;
memset(modd.arr,0,sizeof(modd.arr)); //matrix modd is initialized to be a unit matrix
for(i=0;i<n;i++)
modd.arr[i][i]=1;
meven=a; //matrix meven is initialized
if(k==0)
return modd;
else
{
while(k!=1)
{
if(k&1)
{
k--;
modd=mMulti(modd,meven);
}
else
{
k/=2;
meven=mMulti(meven,meven);
}
}
return mMulti(modd,meven);
}
}
int main()
{
int i,j,k;
Matrix A,B,C;
scanf("%d%d%d",&n,&k,&m);
memset(A.arr,0,sizeof(A.arr));
for(i=0;i<n;i++)
for(j=0;j<n;j++)
scanf("%d",&A.arr[i][j]);
memcpy(B.arr,A.arr,sizeof(A.arr));
for(i=0;i<n;i++)
for(j=0;j<n;j++)
A.arr[i][j+n]=A.arr[i][j];
for(i=n;i<2*n;i++)
{
A.arr[i][i]=1;
B.arr[i][i-n]=1;
}
C=mMulti(mPow(A,k-1),B);
/*print the sum*/
for(i=0;i<n;i++)
{
for(j=0;j<n-1;j++)
printf("%d ",C.arr[i][j]);
printf("%d\n",C.arr[i][n-1]);
}
return 0;
}
分享到:
相关推荐
矩阵乘法必用算法快速幂基础程序pascal
经典算法 高效计算快速幂 使用矩阵方式进行计算
需要注意的是,快速幂算法不仅可以用于求解正整数的幂运算,还可以扩展到负整数、小数甚至矩阵的幂运算中。此外,在实际应用中,还需要注意处理底数为0或指数为0的特殊情况,以及考虑取模运算的需求,以满足不同的...
快速幂 快速幂算法在旋翼飞行器控制中的应用并非直接关联,快速幂作为一种高效的数学算法...例如,在设计某种迭代算法时,若需快速求解矩阵指数函数(如系统动态模型矩阵的指数形式),这时快速幂算法就可以派上用场。
关于矩阵构造与快速幂的算法介绍与教程。。
在讲解快速幂之前,让我们先来思考一个问题:7的10次方,怎样算比较快?...这次的讲解就到这里了,希望大家对快速幂能有所了解,快速幂还包涵矩阵快速幂,快速幂的代码是需要背的,如果要熟练的话就只能多背!
这种算法称为快速近似算法幂迭代(API)方法,保证了算法的正交性每次迭代的子空间加权矩阵。此外,它还执行了许多与幂迭代相关的子空间跟踪方法,如pass、NIC、NP3和OPAST,同时同样的计算复杂度。API方法是为指数...
利用了矩阵结合律,先算出构造递推矩阵自乘的结果,再与初始矩阵相乘。 #include using namespace std; typedef long long ll; #define ls (o<<1) #define rs (o<<1|1) #define pb push_back //#define...
自从RSA算法提出后,方幂模快速算法一直是研究重点之一,方幂模算法的改进和速度的提高直接影响RSA算法的整体性能和广泛应用。深入分析了方幂模计算的秦九韶算法、分块算法、二进制自适应分组查表法和最短加法链算法...
28.2 矩阵求逆 28.3 对称正定矩阵和最小二乘逼近 思考题 本章注记 第29章 线性规划 29.1 标准型和松弛型 29.2 将问题表达为线性规划 29.3 单纯形算法 29.4 对偶性 29.5 初始基本可行解 ...
给出了分数阶傅立叶变换( FRFT) 的定义 ,介绍了已有的几种离散 ... 并且在改变分数阶幂时不需重新计算整个过程 ,只需计算一个对角矩阵. 为与其他方法作比较 ,作者最后对几个典型信号作了计算机仿真 ,并给出其仿真结果.
代数算法:方幂和、霍纳法则计算多项式和、矩阵乘法(2种)、方阵的LUP分解、解线性方程组(2种)、矩阵求逆(2种)、求伪逆矩阵(2种)、解正态方程组(2种)、最小二乘估计(2种)、快速傅里叶变换、快速傅里叶逆...
霍纳法则计算多项式和、矩阵乘法(2种)、方阵的LUP分解、解线性方程组(2种)、矩阵求逆(2种)、求伪逆矩阵(2种)、解正态方程组(2种)、最小二乘估计(2种)、多元最小二乘估计*、快速傅里叶变换、快速傅里叶逆...
9.2 求幂运算 9.3 欧几里得算法 9.4 多项式乘法 9.5 矩阵乘法 9.5.1 Winograd算法 9.5.2 Strassen算法 9.5.3 布尔矩阵 9.6 快速傅里叶变换 9.7 小结 第10章 归约 10.1 引言 10.2 归约的例子 10.2.1 简单...
该方法利用一个介于信号和噪声特征值之间的分界值将特征空间分成两个子空间,并用矩阵幂乘和此分界值的有理式逼近这两个子空间的投影矩阵,将此投影矩阵代入到ESB算法的权值求解式中,在不降低性能的前提下,可大大...
4.6.2 快速排序算法示例 114 4.7 堆排序法 116 4.7.1 堆排序算法 116 4.7.2 堆排序算法示例 121 4.8 合并排序法 123 4.8.1 合并排序算法 123 4.8.2 合并排序算法示例 126 4.9 排序算法的效率 129 4.10 排序...
·快速排序(第7.1节)中用到的划分方法与期望线性时间顺序统计算法(expected linear-time order-statistic algorithm,第9.2节)有所变化。现在,我们采用了Lomuto提出的方法,并将该方法与指示器随机变量一起使用,...
在该算法中,为了快速构建邻域矩阵,设计并实现了基于精确欧式位置敏感哈希的近邻搜索并行算法;为了实现特征值的快速求解,设计并实现了基于幂法和降阶法交替执行的特征值求解并行算法.为了进一步提高算法的性能,基于...
简单的数论算法,包含了快速幂,矩阵快速幂的c++模板
程序猿可能都知道 数据结构 + 算法 = 程序 ,慧眼识金的人懂得下下载这本算法导论的想必也知道它的经典,这是本清晰度还不错的pdf版本,外面好多资源,但都有内容不全的问题,这本是难得的全书,不用费力下载part ...