矩阵加速
【模板】矩阵加速（数列）
作用
有这样一种问题，要你求斐波那契数列的第$n$项，但是这个$n$可以大到$int64$的大小（$2^{61}-1$），还会有若干次询问，这么多次询问还要你1s内出所有答案，传统的for循环肯定GG，于是这时候就需要矩阵加速啦（利用矩阵运算+矩阵快速幂来加速递推求解过程）
- 那么这里就需要特别注意一点，那就是矩阵的左乘和右乘，这一点在快速幂函数中必须必须要注意，如果写反了就错了（按照个人习惯来，我比较习惯构造一个矩阵，然后让初始向量左乘它）
原理
对于模板题，我们可以很容易得到这样一个矩阵，它满足
于是，我们观察左侧向量的第一个数，初始为$a_1$，左乘一次矩阵得到$a_2$，所以左乘$n-1$次矩阵可以得到$a_n$，应用矩阵快速幂，打出如下代码
代码
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
47
48
| #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
struct M{
ll mat[15][15];
}a;
M operator*(M x1,M x2){
M res;
memset(res.mat,0,sizeof(res));
for(int i=1;i<=3;i++){
for(int j=1;j<=3;j++){
for(int k=1;k<=3;k++){
res.mat[i][j]+=(x1.mat[i][k]%mod*x2.mat[k][j]%mod)%mod;
res.mat[i][j]%=mod;
}
}
}
return res;
}
inline M qpow(M a,ll y,M ans){
M base=a;
while(y>0){
if(y&1) ans=ans*base;
y>>=1;
base=base*base;
}
return ans;
}
int main(){
int t;
cin>>t;
while(t--){
ll nn;
cin>>nn;
memset(a.mat,0,sizeof(a));
M b;
memset(b.mat,0,sizeof(b));
b.mat[1][1]=b.mat[1][2]=b.mat[1][3]=1;
a.mat[1][1]=a.mat[1][2]=a.mat[2][2]=a.mat[2][3]=a.mat[3][1]=0;
a.mat[1][3]=a.mat[2][1]=a.mat[3][2]=a.mat[3][3]=1;
M ans=qpow(a,nn-1,b);
cout<<ans.mat[1][1]<<endl;
}
return 0;
}
|
习题
观察得矩阵
AC代码
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
| #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
struct M{
ll mat[15][15];
}a;
M operator*(M x1,M x2){
M res;
memset(res.mat,0,sizeof(res));
for(int i=1;i<=2;i++){
for(int j=1;j<=2;j++){
for(int k=1;k<=2;k++){
res.mat[i][j]+=(x1.mat[i][k]%mod*x2.mat[k][j]%mod)%mod;
res.mat[i][j]%=mod;
}
}
}
return res;
}
inline M qpow(M a,ll y,M ans){
M base=a;
while(y>0){
if(y&1) ans=ans*base;
y>>=1;
base=base*base;
}
return ans;
}
int main(){
ll nn;
cin>>nn;
memset(a.mat,0,sizeof(a));
M b;
memset(b.mat,0,sizeof(b));
b.mat[1][1]=b.mat[1][2]=1;
a.mat[1][1]=0;
a.mat[1][2]=a.mat[2][1]=a.mat[2][2]=1;
M ans=qpow(a,nn-1,b);
cout<<ans.mat[1][1]<<endl;
return 0;
}
|
就是把系数改成了$p$和$q$而已，太简单了，矩阵转移如下
AC代码
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
| #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll p,q,a1,a2,n,mod;
struct M{
ll mat[15][15];
}a;
M operator*(M x1,M x2){
M res;
memset(res.mat,0,sizeof(res));
for(int i=1;i<=2;i++){
for(int j=1;j<=2;j++){
for(int k=1;k<=2;k++){
res.mat[i][j]+=(x1.mat[i][k]%mod*x2.mat[k][j]%mod)%mod;
res.mat[i][j]%=mod;
}
}
}
return res;
}
inline M qpow(M a,ll y,M ans){
M base=a;
while(y>0){
if(y&1) ans=ans*base;
y>>=1;
base=base*base;
}
return ans;
}
int main(){
cin>>p>>q>>a1>>a2>>n>>mod;
memset(a.mat,0,sizeof(a));
M b;
memset(b.mat,0,sizeof(b));
b.mat[1][1]=a1;
b.mat[1][2]=a2;
a.mat[1][1]=0;
a.mat[1][2]=q;
a.mat[2][1]=1;
a.mat[2][2]=p;
M ans=qpow(a,n-1,b);
cout<<ans.mat[1][1]<<endl;
return 0;
}
|