1.整数快速幂
计算 a^p
a ^ p =a ^ ( k * d + c ) = ( a ^ k) ^ d * a ^ c;
e.g. 2 ^ 5 = ( 2 ^ 2 ) ^ 2 * 2 ^ 1 计算次数减少
对应p的二进制位，若该二进制位为1， ans乘上该位的res幂次，每二进制位乘上该位幂次 res*=res
//整数快速幂 计算a^p ll qpow(ll a, ll p) { ll ans=1, res=a; while(p) { if(p&1) { ans*=res; //p该二进制位为1 乘上幂次 } res*=res; // 二进制位幂次相乘 p>>=1; } return ans; }
2.矩阵快速幂
矩阵a，b相乘要满足条件：a的行数==b的列数
类似整数快速幂 把整数相乘替换乘矩阵相乘
//矩阵快速幂 struct Mat { ll x[N][N]; }; Mat c; ll n; Mat multi(Mat a, Mat b) { Mat tmp; mem(tmp.x); fo(i,n) fo(j,n) fo(k,n) tmp.x[i][j]+=a.x[i][k]*b.x[k][j]; return tmp; } Mat m_qpow(Mat a, ll p) { //整数乘法替换成矩阵乘法 fo(i,n) c.x[i][i]=1; Mat ans=c, res=a; while(p) { if(p&1) { ans=multi(ans,res); } res=multi(res,res); p>>=1; } return ans; }
原文：https://www.cnblogs.com/op-z/p/10778932.html