矩阵快速幂小专题复习

一个关于矩阵快速幂的小专题题解汇总
专题链接:here we go!



A hdu 1757
题面:
Lele now is thinking about a simple function f(x).

If x < 10 f(x) = x.
If x >= 10 f(x) = a0 f(x-1) + a1 f(x-2) + a2 f(x-3) + …… + a9 f(x-10);
And ai(0<=i<=9) can only be 0 or 1 .

Now, I will give a0 ~ a9 and two positive integers k and m ,and could you help Lele to caculate f(k)%m.
Input
The problem contains mutiple test cases.Please process to the end of file.
In each case, there will be two lines.
In the first line , there are two positive integers k and m. ( k<2*10^9 , m < 10^5 )
In the second line , there are ten integers represent a0 ~ a9.
Output
For each case, output f(k) % m in one line.
Sample Input
10 9999
1 1 1 1 1 1 1 1 1 1
20 500
1 0 1 0 1 0 1 0 1 0
Sample Output
45
104

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
//hdu 1757
/*Sample Input
10 9999
1 1 1 1 1 1 1 1 1 1
20 500
1 0 1 0 1 0 1 0 1 0
Sample Output
45
104*/
#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;
}

这题不想讲 因为我没看 就这么任性(没有啦,这是暑假做的,最近只是把没做的补上了而已 最近做的基本方程也都写进了注释

ok 下一题:
B:题面
A为一个方阵,则Tr A表示A的迹(就是主对角线上各项的和),现要求Tr(A^k)%9973。
Input
数据的第一行是一个T,表示有T组数据。
每组数据的第一行有n(2 <= n <= 10)和k(2 <= k < 10^9)两个数据。接下来有n行,每行有n个数据,每个数据的范围是[0,9],表示方阵A的内容。
Output
对应每组数据,输出Tr(A^k)%9973。
Sample Input
2
2 2
1 0
0 1
3 99999999
1 2 3
4 5 6
7 8 9
Sample Output
2
2686
上code不解释:

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;
}

C 题面:
斐波那契数列的定义如下:

F(0) = 0
F(1) = 1
F(n) = F(n - 1) + F(n - 2) (n >= 2)

(1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, …)
给出n,求F(n),由于结果很大,输出F(n) % 1000000009的结果即可。
Input
输入1个数n(1 <= n <= 10^18)。
Output
输出F(n) % 1000000009的结果。
Sample Input
11
Sample Output
89
code:

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;
}

说到斐波拉契不妨多说几句:
斐波拉契向来是举证快速幂里问烂的问题
就比如nyoj的又见斐波拉契
链接:https://www.nowcoder.com/acm/contest/105/G
来源:牛客网

题目描述
这是一个加强版的斐波那契数列。
给定递推式
求F(n)的值,由于这个值可能太大,请对109+7取模。
输入描述:
第一行是一个整数T(1 ≤ T ≤ 1000),表示样例的个数。
以后每个样例一行,是一个整数n(1 ≤ n ≤ 1018)。
输出描述:
每个样例输出一行,一个整数,表示F(n) mod 1000000007。
示例1
输入
复制
4
1
2
3
100
输出
复制
1
16
57
558616258
AC code:

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;
}

就是扯一下fib啦
看下一题:
D HDU2604
Queues and Priority Queues are data structures which are known to most computer scientists. The Queue occurs often in our daily life. There are many people lined up at the lunch time.

Now we define that ‘f’ is short for female and ‘m’ is short for male. If the queue’s length is L, then there are 2 L numbers of queues. For example, if L = 2, then they are ff, mm, fm, mf . If there exists a subqueue as fmf or fff, we call it O-queue else it is a E-queue.
Your task is to calculate the number of E-queues mod M with length L by writing a program.
Input
Input a length L (0 <= L <= 10 6) and M.
Output
Output K mod M(1 <= M <= 30) where K is the number of E-queues with length L.
Sample Input
3 8
4 7
4 8
Sample Output
6
2
1

ac code:

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;
}

从接下来的E开始就是我这几天做的了
E hdu 2256


Input
The first line of input gives the number of cases, T. T test cases follow, each on a separate line. Each test case contains one positive integer n. (1 <= n <= 10^9)
Output
For each input case, you should output the answer in one line.
Sample Input
3
1
2
5
Sample Output
9
97
841
这个题思路就是
把4次方变成2次方 也就是 (5+2sqrt(6))^n;
最后推到公式也是从这位巨巨博客看的 链接:
https://blog.csdn.net/scf0920/article/details/39377129
然后我也截图了 自己看着也舒服点

上一份我的CODE吧:

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
#include <iostream>
#include <cmath>
#define ll long long
using namespace std;
const int mod = 1024;
struct mat{
ll a[2][2];
};
mat ans,cnt;
mat mul (mat A,mat B){
mat C;
for(int i=0;i<2;i++){
for(int j=0;j<2;j++){
C.a[i][j]=0;
for(int k=0;k<2;k++){
C.a[i][j]+=A.a[i][k]*B.a[k][j]%mod;
C.a[i][j]%=mod;
}
}
}
return C;
}
mat pow(mat wyh,ll n){
mat res,temp=wyh;
for(int i=0;i<4;i++)
for(int j=0;j<4;j++)
if(i==j)res.a[i][j]=1;
else res.a[i][j]=0;
while(n>0){
if(n&1){
res=mul(res,temp);
}
temp=mul(temp,temp);
n>>=1;
}
return res;
}
void init(){
ans.a[0][0]=5;
ans.a[0][1]=12;
ans.a[1][0]=2;
ans.a[1][1]=5;
cnt.a[0][0]=5;
cnt.a[1][0]=2;
}
int main(){
ios::sync_with_stdio(false);
int t;
cin>>t;
while(t--){
init();
int n;
cin>>n;
if(n==1)cout<<"9"<<endl;
else {
mat cnm,_;
cnm=pow(ans,n-1);
_=mul(cnm,cnt);
ll xx;
xx=2*_.a[0][0]-1;
xx%=mod;
cout<<xx<<endl;
}
}
return 0;
}

关于里面的素质用语…不解释不解释啊
下一题哈
codeforces 185A
Dwarfs have planted a very interesting plant, which is a triangle directed “upwards”. This plant has an amusing feature. After one year a triangle plant directed “upwards” divides into four triangle plants: three of them will point “upwards” and one will point “downwards”. After another year, each triangle plant divides into four triangle plants: three of them will be directed in the same direction as the parent plant, and one of them will be directed in the opposite direction. Then each year the process repeats. The figure below illustrates this process.

Help the dwarfs find out how many triangle plants that point “upwards” will be in n years.

Input
The first line contains a single integer n (0 ≤ n ≤ 1018) — the number of full years when the plant grew.

Please do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use cin, cout streams or the %I64d specifier.

Output
Print a single integer — the remainder of dividing the number of plants that will point “upwards” in n years by 1000000007 (109 + 7).

Examples
Input
1
Output
3
Input
2
Output
10
Note
The first test sample corresponds to the second triangle on the figure in the statement. The second test sample corresponds to the third one.
这个题我日吗写了四次
从回合肥的飞机上就开始写 前后错了好多次哦
之前是矩阵弄错了 上网查了哈之后发现可以用快速幂做,但是我两种方法都做了
在这里共大家参考 然后公式推导写在注释里了
公式+快速幂:

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
//f(n)=2^(2n-1)+2^(n-1);
//f(n)=3f(n-1)+g(n-1)
//g(n)=3g(n-1)+f(n-1)
//f(n)+g(n)=4^n;
//f(n)-g(n)=2^n;
//联立求解
#include <iostream>
#define ll long long
using namespace std;
const int mod=1e9+7;
ll quick_mod(ll a,ll n){
ll ans=1;
a%=mod;
while(n){
if(n&1){
ans=ans*a;
ans%=mod;
}
a=a*a;
a%=mod;
n/=2;
}
return ans;
}
int main(){
ios::sync_with_stdio(false);
ll n;
cin>>n;
if(n==0){
cout<<"1";
}
else cout<<(quick_mod(2,2*n-1)+quick_mod(2,n-1))%mod<<endl;
return 0;
}

矩阵快速幂:

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
//重新再试一发矩阵快速幂做法
#include <iostream>
#include <cstring>
#define ll long long
using namespace std;
const int mod=1e9+7;
struct mat{
ll aa[2][2];
mat(){
memset(aa,0,sizeof(aa));
}
};
mat ans,cnt;
mat mmul(mat &a,mat &b){
mat c;
for(int i=0;i<2;i++){
for(int j=0;j<2;j++){
c.aa[i][j]=0;
for(int k=0;k<2;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,ll n){
mat b;
b.aa[0][0]=b.aa[1][1]=1;
while(n)
{
if(n&1)b=mmul(b,a);
a=mmul(a,a);
n>>=1;
}
return b;
}
int main(){
ios::sync_with_stdio(false);
ll n;
cin>>n;
ans.aa[0][0]=3;
ans.aa[0][1]=1;
ans.aa[1][0]=1;
ans.aa[1][1]=3;
cnt.aa[0][0]=1;
cnt.aa[1][0]=0;
mat _;
ans=mpow(ans,n);
_=mmul(ans,cnt);
cout<<_.aa[0][0]%mod<<endl;
return 0;
}

G题 hdu2842
Dumbear likes to play the Chinese Rings (Baguenaudier). It’s a game played with nine rings on a bar. The rules of this game are very simple: At first, the nine rings are all on the bar.
The first ring can be taken off or taken on with one step.
If the first k rings are all off and the (k + 1)th ring is on, then the (k + 2)th ring can be taken off or taken on with one step. (0 ≤ k ≤ 7)

Now consider a game with N (N ≤ 1,000,000,000) rings on a bar, Dumbear wants to make all the rings off the bar with least steps. But Dumbear is very dumb, so he wants you to help him.
Input
Each line of the input file contains a number N indicates the number of the rings on the bar. The last line of the input file contains a number “0”.
Output
For each line, output an integer S indicates the least steps. For the integers may be very large, output S mod 200907.
Sample Input
1
4
0
Sample Output
1
10
my code :

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
/*Sample Input
1
4
0
Sample Output
1
10*/
// f(n)=f(n-1)+2f(n-2)+1
#include <iostream>
#include <cstring>
#define ll long long
using namespace std;
const int mod=200907;
struct mat {
ll aa[3][3];
};
mat ii,jj;
mat mul(mat a,mat b){
mat c;
for(int i=0;i<3;i++){
for(int j=0;j<3;j++){
c.aa[i][j]=0;
for(int k=0;k<3;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 n){
mat ans;
memset(ans.aa,0,sizeof(ans.aa));
for(int i=0;i<3;i++)
ans.aa[i][i]=1;
while(n){
if(n&1)ans=mul(ans,a);
a=mul(a,a);
n/=2;
}
return ans;
}
void init(){
ii.aa[0][0]=1;
ii.aa[0][1]=2;
ii.aa[0][2]=1;
ii.aa[1][0]=1;
ii.aa[1][1]=0;
ii.aa[1][2]=0;
ii.aa[2][0]=0;
ii.aa[2][1]=0;
ii.aa[2][2]=1;
jj.aa[0][0]=2;
jj.aa[1][0]=1;
jj.aa[2][0]=1;
}
int main(){
ios::sync_with_stdio(false);
ll n;
while(cin>>n){
if(n==0)break;
else if(n==1)cout<<"1"<<endl;
else if(n==2)cout<<"2"<<endl;
else {
init();
mat _;
ii=pow(ii,n-2);
_=mul(ii,jj);
cout<<_.aa[0][0]%mod<<endl;
}
}
return 0;
}

okk
矩阵快速幂就做了这些题 妈的都一个样 说白了就是数学找公式 代码都是 pow mul init啥的 一个鸟样
okk 告辞
晚上得知了一个非常惨痛的信息,国庆节结束了,一天体验卡特喵的??????我就他娘的一天假????我还写尼玛鸟矩阵快速幂???

心态崩了啊我
难受啊马飞
抱怨归抱怨
大家都在坚持,我又怎可轻言放弃?!

coswindy

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