首页 > 代码库 > 矩阵快速幂 模板与简单讲解
矩阵快速幂 模板与简单讲解
模板
快速幂模板
1 void solve(matrix t,long long o) 2 { 3 matrix e; 4 5 memset(e.a,0,sizeof(e.a)); 6 7 for (int i = 0;i < d;i++) 8 e.a[i][i] = 1; 9 10 while (o)11 {12 if (o & 1)13 {14 e = mul(e,t);15 }16 17 o >>= 1;18 19 t = mul(t,t);20 }21 22 long long res = 0;23 24 for (int i = 0;i < d;i++)25 res = (res + e.a[0][i] * f[d-i-1]) % m;26 27 printf("%lld\n",res);28 }
矩阵相乘代码
1 struct matrix 2 { 3 long long a[20][20]; 4 }; 5 6 matrix mul(matrix x,matrix y) 7 { 8 matrix c; 9 10 for (int i = 0;i < d;i++)11 for (int j = 0;j < d;j++)12 {13 c.a[i][j] = 0;14 15 for (int k = 0;k < d;k++)16 {17 c.a[i][j] = (c.a[i][j] + x.a[i][k] * y.a[k][j] % m) % m;18 }19 }20 21 return c;22 }
简单讲解：
矩阵快速幂，就只是把快速幂中的数改成了矩阵，兰儿其实还是有不同的地方，因为快速幂一般用的是递归实现，但是lrj大大说矩阵快速幂还是用迭代实现比较好。
举一个例子，A^15，可以写成(A^8) * (A^4) * (A^2) * (A^1) 的形式，可以看到8，4，2，1都是2的次幂，所以我们就可以方便的运用位运算。
15：1111，那么每次这个数字右移一位，那么矩阵就平方一次，然后遇到当前的最后一位111k，k & 1 == 1，这个时候结果矩阵就要乘以当前的用于运算的矩阵。
矩阵预算也是挺好理解的，用手算模拟一下就可以了。
矩阵快速幂 模板与简单讲解
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。