快速幂+矩阵快速幂

顾名思义，快速幂就是快速算底数的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 (int a,int 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 (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("%dn",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 ) 看起来是废话，但我们构造矩阵的目的是合理性，只要矩阵符合条件，就可以进行计算。

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

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