快速幂


摸一发快速幂

标准快速幂的原理就是把指数拆成二进制减少乘法次数。直接放代码实现了:

1
2
3
4
5
6
7
8
9
10
int qpow(int a,int b){
int ans=1;
while(b){
if(b&1)
  ans*=a;
a*=a;
b>>=1;
  }
return ans;
}

显然运算量减少了许多。在大指数幂的时候尤为突出。//其实这样能不能做一个推广?在大指数幂的时候用十进制来乘呢?算术运算次数小应该能弥补逻辑运算量太大的不足?

当然在实操中还会用到取模这个操作。我们可以根本不去考虑乘方运算取模法则:

1
2
3
4
5
6
7
8
9
10
11
12
int mi(int a,int b)
{
int ans=1;
a%=mod;
while (b)
{
if (b&1) ans=ans*a%mod;
b>>=1;
a=a*a%mod;
}
return ans;
}

同理我们可以将加法分解为快速加法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
ll multi(ll a,ll b,ll p)
{
a=a%p;
b=b%p;
ll ans=0;
while(b>0)
{
if(b&1==1)
{
ans+=a;
ans%=p;
}
b=b>>1;
a=a+a;
a=a%p;
}
return ans;
}

这算是简单的快速幂变形了。然鹅还有一个大boss:

矩阵快速幂

矩阵运算的朴素算法如下:

1
2
3
4
5
6
7
8
9
10
const int N=100;
int c[N][N];
void multi(int a[][N],int b[][N],int n)
{
memset(c,0,sizeof c);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
for(int k=1;k<=n;k++)
c[i][j]+=a[i][k]*b[k][j];
}

显然此算法的复杂度是O(n^3)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
const int N=10;
int tmp[N][N];
void multi(int a[][N],int b[][N],int n)
{
memset(tmp,0,sizeof tmp);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
for(int k=1;k<=n;k++)
tmp[i][j]+=a[i][k]*b[k][j];
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
a[i][j]=tmp[i][j];
}
int res[N][N];
void Pow(int a[][N],int n)
{
memset(res,0,sizeof res);
for(int i=1;i<=n;i++) res[i][i]=1;
while(n)
{
if(n&1)
multi(res,a,n);//res=res*a;复制直接在multi里面实现了;
multi(a,a,n);//a=a*a
n>>=1;
}
}

res数组初始化就等同于单位矩阵E,最终算出的结果是一个res矩阵。

铜牌爷的写法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
struct matrix
{
ll v[2][2];
matrix()
{
memset(v,0,sizeof(v));
}
matrix operator *(matrix &t)
{
matrix res;
memset(res.v,0,sizeof(res.v));
for(int i=0; i<2; i++)
for(int j=0; j<2; j++)
for(int k=0; k<2; k++)
{
res.v[i][j]+=v[i][k]*t.v[k][j];
res.v[i][j]%=MOD;
}
return res;
}
};
matrix power(matrix a,int b)
{
matrix ans;
memset(ans.v,0,sizeof(ans.v));
ans.v[0][0]=1;
ans.v[1][1]=1;
while(b>0)
{
if(b%2==1)
{
ans*=a;
}
b=b>>1;
a=a*a;
}
return ans;
}

至于应用。。今天就摸了。。改日
可以先看看dalao的应用:

http://blog.csdn.net/wust_zzwh/article/details/52058209