快速幂+矩阵快速幂(总结+例题)
1.快速幂
以求a的b次方来介绍:
首先把b转换成二进制数
该二进制数第i位的权为 2^i - 1 .
比如 : 11的二进制是1011
11 = 2³×1 + 2²×0 + 2¹×1 + 2º×1
所以假设我们要求a^b,那么其实b是可以拆成二进制的,该二进制数第i位的权为2^(i-1),例如当b==11时
a^11=a^(2^0+2^1+2^3)
模板:
ll pow(ll x, ll y) //位运算
{
ll res = 1;
while(y) {
if (y&1) res *= x ; //res才是最终我们要的结果.
x *= x ; //一个中间转移量. y每右移一次, x 就多一个平方.
y=y>>1;
}
return res;
}
2.矩阵快速幂
矩阵:
struct node {
int mat[15][15];//定义矩阵
}x,y;
矩阵乘法:
node mul(node x,node y){//矩阵乘法
node tmp;
for(int i=0;i<len;i++){
for(int j=0;j<len;j++){
tmp.mat [i][j]=0;
for(int k=0;k<len;k++){
tmp.mat [i][j]+=(x.mat [i][k]*y.mat [k][j])%mod;
}
tmp.mat [i][j]=tmp.mat[i][j]%mod;
}
}
return tmp;
}
矩阵快速幂:
node matpow(node x,node y,int num){//矩阵快速幂
while(num){
if(num&1){
y=mul(y,x);
}
x=mul(x,x);
num=num>>1;
}
return y;
}
如何构造矩阵:http://www.cnblogs.com/frog112111/archive/2013/05/19/3087648.html
一些递推式:
例题: