数论基础三--(矩阵快速幂习题

矩阵快速幂习题
学矩阵快速幂差不多了…随便写了几个题,你们随便看看就行
配图:

就不一题一题说了,感觉矩阵快速幂题目都差不多,差异就是状态转移矩阵,找不找得到看命咯被
只放代码了

牛客网——又见斐波拉契
https://www.nowcoder.com/acm/contest/105/G

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int mod=1e9+7;
struct mat
{
ll aa[6][6];
};
mat mul(mat A,mat B)
{
mat C;
for(int i=0;i<6;i++)
{
for(int j=0;j<6;j++)
{
C.aa[i][j]=0;
for(int k=0;k<6;k++)
{
C.aa[i][j]+=A.aa[i][k]*B.aa[k][j]%mod;
C.aa[i][j]%=mod;
}
}
}
return C;
}
mat mpow(mat A,long long n)
{
mat res,temp=A;
for(int i=0;i<6;i++)
for(int j=0;j<6;j++)
{
if(i==j)res.aa[i][j]=1;
else res.aa[i][j]=0;
}

while(n>0){
if(n&1)res=mul(res,temp);
temp=mul(temp,temp);
n>>=1;
}
return res;
}
int main()
{
ios::sync_with_stdio(false);
ll n;
int t;
cin>>t;
while(t--){
cin>>n;
mat A,B;
for(int i=0;i<6;i++)
{
A.aa[0][i]=1;
}
A.aa[1][0]=1;
for(int i=1;i<6;i++)A.aa[1][i]=0;
A.aa[2][0]=0;
A.aa[2][1]=0;
A.aa[2][2]=1;
A.aa[2][3]=3;
A.aa[2][4]=3;
A.aa[2][5]=1;
for(int i=0;i<3;i++)
A.aa[3][i]=0;
A.aa[3][3]=1;
A.aa[3][4]=2;
A.aa[3][5]=1;
for(int i=0;i<4;i++)A.aa[4][i]=0;
A.aa[4][4]=1;
A.aa[4][5]=1;
for(int i=0;i<5;i++)
A.aa[5][i]=0;
A.aa[5][5]=1;
B.aa[0][0]=1;
B.aa[1][0]=0;
B.aa[2][0]=8;
B.aa[3][0]=4;
B.aa[4][0]=2;
B.aa[5][0]=1;
/*for(int i=0;i<6;i++)
{
for(int j=0;j<6;j++)
{
if(j!=5)cout<<A.aa[i][j]<<" ";
else cout<<A.aa[i][j]<<endl;
}
}*/
if(n<=1)cout<<n<<endl;
else {
mat wyh;
wyh=mpow(A,n-1);
mat ans;
ans=mul(wyh,B);
cout<<ans.aa[0][0]%mod<<endl;
}
}
return 0;
}

HDU1757:http://acm.hdu.edu.cn/showproblem.php?pid=1757

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include <iostream>
#include <cstring>
#define ll long long
using namespace std;
struct mat
{
ll aa[10][10];
mat()
{
memset(aa,0,sizeof(aa));
}
};
mat mul(mat A,mat B,ll m)
{
mat C;
for(int i=0;i<10;i++)
{
for(int j=0;j<10;j++)
{
for(int k=0;k<10;k++)
{
C.aa[i][j]+=(A.aa[i][k]*B.aa[k][j])%m;
C.aa[i][j]%=m;
}
}
}
return C;
}
mat pow(mat A,ll k,ll m){
mat res;
mat temp=A;
for(int i=0;i<10;i++)
{
res.aa[i][i]=1;
}
while(k>0){
if(k&1){
res=mul(res,temp,m);
}
temp=mul(temp,temp,m);
k>>=1;
}
return res;
}
int main(){
ios::sync_with_stdio(false);
mat wyh;
for(int i=1;i<10;i++)
wyh.aa[i][i-1]=1;
ll k,m;
while(cin>>k>>m){


mat ans;
for(int i=0;i<10;i++)
{
cin>>wyh.aa[0][i];
}
if(k<=9)
{
cout<<k<<endl;
}
else
/*for(int i=0;i<10;i++)
{
ans.aa[i][0]=9-i;
}*/
/*for(int i=0;i<10;i++)
cout<<ans.aa[i][0]<<endl;*/
{
ans=pow(wyh,k-9,m);
ll sum=0;
for(int i=0;i<10;i++){
sum+=ans.aa[0][i]*(9-i);
}
cout<<sum%m<<endl;
}

}
return 0;
}

hdu 1575:
http://acm.hdu.edu.cn/showproblem.php?pid=1575

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <iostream>
#define ll long long
using namespace std;
const int mod=9973;
struct mat{
ll aa[10][10];
};
ll n,k;
mat mul(mat A,mat B){
mat C;
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
C.aa[i][j]=0;
for(int k=0;k<n;k++){
C.aa[i][j]+=A.aa[i][k]*B.aa[k][j]%mod;
C.aa[i][j]%=mod;
}
}
}
return C;
}
mat pow(mat A,ll k){
mat res;
mat temp=A;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
if(i==j)res.aa[i][j]=1;
else res.aa[i][j]=0;

while(k>0){
if(k&1)res=mul(res,temp);
temp=mul(temp,temp);
k>>=1;
}
return res;
}
int main()
{
ios::sync_with_stdio(false);
int t;
cin>>t;
while(t--){
cin>>n>>k;
mat ans;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
cin>>ans.aa[i][j];

mat wyh;
wyh=pow(ans,k);
ll sum=0;
for(int i=0;i<n;i++)
{
sum+=wyh.aa[i][i];
sum%=mod;
}
cout<<sum<<endl;
}
return 0;
}

51nod 1242:
https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1242

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 <iostream>
#include <cstring>
#include <cstdio>
#define ll long long
using namespace std;
const ll maxn=1000000009;
struct map{
ll m[2][2];
map(){
memset(m,0,sizeof(m));
}
};
map mul(map &a,map &b)
{
map c;
for(int i=0;i<2;i++)
for(int j=0;j<2;j++)
for(int k=0;k<2;k++)
c.m[i][j]=(c.m[i][j]+a.m[i][k]*b.m[k][j])%maxn;
return c;
}
map pow(map a,ll n)
{
map b;
b.m[0][0]=b.m[1][1]=1;
while(n)
{
if(n&1)b=mul(b,a);
a=mul(a,a);
n>>=1;
}
return b;
}
int main()
{
ios::sync_with_stdio(false);
ll n;
cin>>n;
map a;
a.m[0][0]=a.m[0][1]=a.m[1][0]=1;
//a.m[1][1]=0;
map aa=pow(a,n);
//printf("%lld\n",aa.m[1][0]);
cout<<aa.m[1][0]<<endl;
return 0;
}

hdu 2604:
https://vjudge.net/contest/243691#problem/D

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <iostream>
#define ll long long
using namespace std;
ll l,m;
struct mat
{
ll aa[4][4];
};
mat ans,cnt;
mat mul(mat a,mat b)
{
mat c;
for(int i=0;i<4;i++)
for(int j=0;j<4;j++)
{
c.aa[i][j]=0;
for(int kk=0;kk<4;kk++)
{
c.aa[i][j]+=a.aa[i][kk]*b.aa[kk][j]%m;
c.aa[i][j]%=m;
}
}
return c;
}
mat pow(mat a,ll l){
mat res,temp=a;
for(int i=0;i<4;i++)
for(int j=0;j<4;j++)
if(i==j)res.aa[i][j]=1;
else res.aa[i][j]=0;
while(l>0){
if(l&1){
res=mul(res,temp);
}
temp=mul(temp,temp);
l>>=1;
}
return res;
}
void init(){
for(int i=0;i<4;i++)
ans.aa[0][i]=1;
ans.aa[0][1]=0;
for(int i=1;i<4;i++)
for(int j=0;j<4;j++)
{
if(i==j+1)ans.aa[i][j]=1;
else ans.aa[i][j]=0;
}
cnt.aa[0][0]=9;
cnt.aa[1][0]=6;
cnt.aa[2][0]=4;
cnt.aa[3][0]=2;
}

int main(){
ios::sync_with_stdio(false);
while(cin>>l>>m){
init();
if(l==0)cout<<"0"<<endl;
else if(l<=4)cout<<cnt.aa[4-l][0]%m<<endl;
else{
mat wyh;
wyh=pow(ans,l-4);
mat king;
king =mul(wyh,cnt);
cout<<king.aa[0][0]<<endl;
}
}
return 0;
}

只放这些吧 都是入门题,后面如果我还做矩阵快速幂再加进来。

百度之星初赛被教育了…O-O

coswindy

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