整数快速幂与矩阵快速幂
前言
公众号菜单栏新增“精选文章”选项，欢迎使用！
一、整数快速幂
顾名思义，快速幂就是快速算底数的n次幂。其时间复杂度为 O(log₂N)， 与朴素的O(N)相比效率有了极大的提高。
核心思想：求解12^11，等价于求解12 ^ (2 ^ 0+2 ^ 1+2 ^ 3)
代码：
typedef long long llll fastpow(ll x,ll y) { //求取x^y
ll res=1;
while(y) {
if(y % 2==1) { //为奇数，当前最低位为1，res就要乘以当前位置的权重
res *= x;
}
x *= x; //每右移一次，最低位的权重都要乘以x
y /= 2; //右移
}
return res;
}二、矩阵快速幂
矩阵快速幂和整数快速幂的思想一致，只不过答案矩阵的初始状态不再是整数1，而是一个单位矩阵：单位矩阵在矩阵乘法中的作用等同于整数中的1。
定义矩阵：
struct matrix {
ll mat[6][6];
init() {
memset(mat, 0, sizeof(mat));
}
};定义矩阵乘法：
matrix mul(matrix a, matrix b) { //return a*b
matrix c;
c.init();
for(int i = 0; i < 6; i++) {
for(int j = 0; j < 6; j++) {
for(int k = 0; k < 6; k++) {
c.mat[i][j] += ((a.mat[i][k] % mod) * (b.mat[k][j] % mod)) % mod;
c.mat[i][j] %= mod;
}
}
}
return c;
}定义矩阵快速幂：
matrix fast_pow(matrix A, int n) { //return A^n % mod
matrix B;
B.init();
for(int i = 0; i < 6; i++) { //单位矩阵
B.mat[i][i] = 1;
}
while(n) {
if(n & 1) {
B = mul(B, A);
}
A = mul(A, A);
n >>= 1;
}
return B;
}本文参与 腾讯云自媒体同步曝光计划，分享自微信公众号。
原始发表：2021-12-10，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
