快速幂
时间复杂度：O (logN)
模板题：蓝桥杯省赛无忧班（C&C++
组）第 1 期 - 快速幂 - 蓝桥云课 (lanqiao.cn)
二进制解法
1
2
3
4
5
6
7
8
9
| ll qpow(ll a, ll n){
ll ans = 1;
while(n){
if(n&1) ans = (ans*a)%MOD;
a = (a*a)%MOD;
n >>= 1;
}
return ans;
}
|
递归解法
1
2
3
4
5
6
7
8
| ll qpow(const ll & a,const ll & n){
if(n == 0) return 1;
else if(n & 1) return (qpow(a,n-1)*a) % MOD;
else{
ll temp = qpow(a,n/2) % MOD;
return (temp*temp) % MOD;
}
}
|
矩阵快速幂
基础
模板题：P3390
【模板】矩阵快速幂 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
矩阵
要求矩阵的幂，我们首先要有一个 NxN
的矩阵结构体，并重定义矩阵的乘法：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| ll n;
struct matrix{
ll a[maxn][maxn];
matrix(ll e = 0){
for(int i = 0 ; i < n ; i ++){
for(int j = 0 ; j < n ; j ++){
a[i][j] = e*(i == j);
}
}
}
matrix operator*(const matrix & rhs){
matrix res(0);
for(int i = 0 ; i < n ; i ++){
for(int j = 0 ; j < n ; j ++){
for(int k = 0 ; k < n ; k ++){
res.a[i][j] = (res.a[i][j] + a[i][k]*rhs.a[k][j]) % mod;
}
}
}
return res;
}
};
|
快速幂
自定义矩阵乘法后，和整数快速幂类似地，我们可以得到如下的快速幂函数：
1
2
3
4
5
6
7
8
9
| matrix qpow(matrix m, ll t){
matrix res(1);
while(t){
if(t & 1) res = res*m;
m = m*m;
t >>= 1;
}
return res;
}
|
主函数
求给定矩阵的k次幂
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| cin>>n>>k;
matrix temp(0);
for(int i = 0 ; i < n ; i ++){
for(int j = 0 ; j < n ; j ++){
cin>>temp.a[i][j];
}
}
matrix ans = qpow(temp,k);
for(int i = 0 ; i < n ; i ++){
cout<<ans.a[i][0];
for(int j = 1 ; j < n ; j ++){
cout<<" "<<ans.a[i][j];
}
cout<<"\n";
}
|
求斐波那契数列
蓝桥杯省赛无忧班（C&C++
组）第 1 期 - 斐波那契数列 - 蓝桥云课 (lanqiao.cn)
矩阵快速幂可以以 指数级 加速求和操作，例如：求斐波那契数列。
由
我们可以得到公式： \[
\begin{bmatrix}
F(n)\\
F(n-1)
\end{bmatrix} =
\begin{bmatrix}
1 & 1\\
1 & 0
\end{bmatrix}^{n-1} *
\begin{bmatrix}
f(1) \\
f(0)
\end{bmatrix}
\]
代码
1
2
3
4
5
6
7
| ll fib(ll x){
if(x == 0 || x == 1) return 1;
matrix res(0);
res.a[0][0] = res.a[1][0] = res.a[0][1] = 1;
res = qpow(res,x-1);
return (res.a[0][0] + res.a[0][1]) % mod;
}
|