快速幂+矩阵快速幂

快速幂

顾名思义,快速幂就是快速算底数的n次幂。其时间复杂度为 O(log₂N), 与朴素的O(N)相比效率有了极大的提高。

以a^b为例,假设b=11,则
$$
a^{11}=a^{2^{0}+2^{1}+2^{3}}
$$
因为11的二进制为1011,11=2^0 +2^1+2^3,所以可得上式。

所以我们只要判断幂的二进制的值,就可以计算在log()级别的时间求解出答案。

1
2
3
4
5
6
7
8
9
10
int mod;
int mulpow(int a,int n){//求a^n
int res=1;
while(n>0){
if(n&1) res=res*a%mod;//如果当前位为1,则进行计算
a=a*a%mod;//a^(2^i),i为循环次数
n/=2;
}
return res;
}

函数中间的运算数可能超过int的范围,所以当我们使用时要注意数据范围而选取适当的数据类型(int,long long)。

矩阵快速幂

矩阵快速幂思想和快速幂一样,只不过由单纯的数字运算变成了矩阵运算(这里需要了解矩阵的运算方法)。

使用矩阵快速幂的场合一般为知道递推式,求解相应的第n项的值。

下面以这个式子为样例,来进行矩阵快速幂的讲解。
$$
a_{n}=2*a_{n-1}+1
$$
我们用这个式子构造一个矩阵:
$$
\left[
\begin{matrix}
a_n \\
1
\end{matrix}
\right]
=
\left[
\begin{matrix}
2 & 1 \\
0 & 1
\end{matrix}
\right]
*
\left[
\begin{matrix}
a_{n-1}\\
1
\end{matrix}
\right]
$$
如果没学过矩阵运算的相关知识,可以去百度进行学习。

然后我们继续递推:
$$
\left[
\begin{matrix}
a_{n-1} \\
1
\end{matrix}
\right]
=
\left[
\begin{matrix}
2 & 1 \\
0 & 1
\end{matrix}
\right]
*
\left[
\begin{matrix}
a_{n-2}\\
1
\end{matrix}
\right]
$$

$$

$$

$$
\left[
\begin{matrix}
a_2 \\
1
\end{matrix}
\right]
=
\left[
\begin{matrix}
2 & 1 \\
0 & 1
\end{matrix}
\right]
*
\left[
\begin{matrix}
a_{1} \\
1
\end{matrix}
\right]
$$

所以
$$
\left[
\begin{matrix}
a_n \\
1
\end{matrix}
\right]
=
{\left[
\begin{matrix}
2 & 1 \\
0 & 1
\end{matrix}
\right]}^{n-1}
*
\left[
\begin{matrix}
a_{1}\\
1
\end{matrix}
\right]
$$
所以我们只需要求出中间的矩阵的结果就可以求出答案。

其大致步骤和快速幂一样。

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
39
40
41
42
43
44
45
46
struct node{
int x[5][5];//一般构造的矩阵大小不会超过5,大小根据情况而定
};

int mod,n,a1;
node ope(node a,node b){//注意函数返回类型为 node,下面的 mulpow()函数返回类型同样是 node;
node r;
for(int i=0;i<2;i++){
for(int j=0;j<2;j++){
r.x[i][j]=0;
for(int k=0;k<2;k++){//这里是矩阵乘法的运算方法
r.x[i][j]+=a.x[i][k]*b.x[k][j];
}
}
}
return r;
}
node mulpow(node a,int n){
//这里用到了一个知识,一个矩阵乘以单位矩阵结果仍为原矩阵,所以这一步相当于快速幂里面的 res=1,具体详见百度百科 单位矩阵
node res;
for(int i=0;i<2;i++){
for(int j=0;j<2;j++)
if(i==j) res.x[i][j]=1;
else res.x[i][j]=0;
}

while(n>0){
if(n&1) res=ope(res,a);
a=ope(a,a);
n/=2;
}
return res;
}
void solve(){
//构造需要求幂的初始矩阵
node a;
a.x[0][0]=2;
a.x[0][1]=a.x[1][1]=1;
a.x[1][0]=0;

node s=mulpow(a,n-1);

//最后一步矩阵乘法,参考前面最后展示的一个的矩阵
int res = s.x[0][0] * a1 + s.x[0][1];
printf("%d\n",res);
}

矩阵乘法也几乎是模板,其难点在于矩阵的构造,给你一个递推式,你必须推出相应的矩阵才可以进行运算,因此需要多学习一些矩阵的知识。

接下来展示一个Fibonacci的递推矩阵:

Fibonacci的定义式:
$$
F(1)=f(2)=1\
F(n)=F(n-1)+F(n-2) (n>2)
$$

递推矩阵:
$$
\left[
\begin{matrix}
F(n)\\
F(n-1)
\end{matrix}
\right]
=
\left[
\begin{matrix}
1 & 1\\
1 & 0
\end{matrix}
\right]
*
\left[
\begin{matrix}
F(n-1)\\
F(n-2)
\end{matrix}
\right]
$$
虽然这这个矩阵的第二个运算式子 F( n - 1 )=F( n - 1 ) 看起来是废话,但我们构造矩阵的目的是合理性,只要矩阵符合条件,就可以进行计算。

计算这个式子时需要注意矩阵快速幂的指数。

相关题目可以百度进行搜索。

感谢您的支持
-------------本文结束感谢您的阅读-------------