两道 矩阵 题目

本文从WordPress迁移而来, 查看全部WordPress迁移文章

poj 3233 Matrix Power Series

题意:略

用了两种方法做这题,区别在于你怎么用数学的方法去分析它

1
2
3
1.设sk = A * A^2 + A^3 + A^4.......+ A^k
sk = (sk-1 + 1) * A;
sk = A * sk-1 + A;

这是个线性方程,就这种方程,构造一个矩阵,然后用矩阵快速幂能很快求出第k项

只不过,这里的sk,sk-1,A,不是普通的数字,而是一个矩阵,但是不妨碍,我们先当它是数字,我们要怎么做

1
2
3
构造矩阵 | sk-1 , 1 |
构造矩阵 | A , 0 |
| A , 1 |

这两个矩阵相乘 可以得到矩阵 | sk , 1 |

1
2
所以 | s1 , 1 |  *  | A , 0 |^(K-1)  =   |sk , 1|
| A , 1 |

然后从数字回到矩阵,s1 = A,0指的是0矩阵,1指的不是1矩阵,而是单位矩阵

也就是我们以A,0矩阵,单位矩阵,构造出一个新矩阵,对它做k-1次矩阵幂就可以求出了

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
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std;
#define MAXSIZE 60
#define INF 0x3f3f3f3f

int MOD;

class matrix{

//为了方便操作,数据域为public
public:
//定义矩阵类型,常用的是int,long long,double
typedef int elemtype;
int row,col;
elemtype a[MAXSIZE][MAXSIZE];

public:
matrix(){}
matrix(int r,int c):row(r),col(c){}
~matrix(){}

//重新设置行列
void reset(int r,int c){ row = r; col = c; }
//将矩阵设为0矩阵
void zero(){ memset(a,0,sizeof(a)); }
//将矩阵设为1矩阵
void one(){
for(int i = 0; i < row; i++)
for(int j = 0; j < col; j++)
a[i][j] = 1;
}
//将矩阵设为单位矩阵
void identity(){
memset(a,0,sizeof(a));
for(int i = 0; i < MAXSIZE; i++) a[i][i] = 1;
}

//重载 = + - * 运算符,其中 + - * 都是取模的
//如果题目不需要取模,可以把 %MOD 去掉
//或者把 MOD 设置得很大,因为不用取模,意味着运算结果不会太大
void add_sub(const matrix &temp,matrix &now,bool isadd){
elemtype flag = isadd ? 1 : -1;
for(int i = 0; i < row; i++)
for(int j = 0; j < col; j++)
now.a[i][j] = (a[i][j]+flag*temp.a[i][j]) % MOD;
}

//保证 A.row = B.row , A.col = B.col
void operator = (const matrix &temp){
row = temp.row; col = temp.col;
for(int i = 0 ; i < row; i++)
for(int j = 0; j < col; j++)
a[i][j] = temp.a[i][j];
}

//保证 A.row = B.row , A.col = B.col
matrix operator + (const matrix &temp){
matrix now(row,col);
add_sub(temp,now,true);
return now;
}

//保证 A.row = B.row , A.col = B.col
matrix operator - (const matrix &temp){
matrix now(row,col);
add_sub(temp,now,false);
return now;
}

//保证 A.col = B.row
matrix operator * (const matrix &temp){
matrix now(row,col);
now.zero();
for(int i = 0; i < row; i++)
for(int j = 0; j < col; j++)
for(int k = 0; k < col; k++)
now.a[i][j] = (now.a[i][j] + a[i][k] * temp.a[k][j]) % MOD;
return now;
}

// 快速幂,操作的结果是保存在now中,不改变自身
matrix operator ^ (int m){
matrix now(row,col);
matrix temp = (*this);
now.identity(); //设为单位矩阵
while(m){
if(m&1) now = now * temp;
temp = temp*temp;
m /= 2;
}
return now;
}
};


int main(){
matrix A(0,0),M(0,0),B(0,0);
int n,m;
while(scanf("%d%d%d",&n,&m,&MOD)!=EOF){
A.reset(n,2*n);
M.reset(2*n,2*n);
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++){
scanf("%d",&A.a[i][j]);
A.a[i][j] %= MOD;
A.a[i][j+n] = i == j ? 1 : 0;
M.a[i][j] = A.a[i][j];
M.a[i+n][j] = A.a[i][j];
M.a[i][j+n] = 0;
M.a[i+n][j+n] = i == j ? 1 : 0;
}
B = A * (M ^ (m-1));
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++)
printf("%d ",B.a[i][j]);
puts("");
}
}
return 0;
}

二分

设 sk = A + A^2 + A^3 + A^4 ……… + A^k

若 k为奇数,sk = sk-1 + A^k

若 k为偶数,sk = s(k/2) * (A^(k/2) + 1) 1是单位矩阵

可见,可以二分,对于k为奇数,变为求sk-1,对于k为偶数,二分求s(k/2)

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
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std;
#define MAXSIZE 60
#define INF 0x3f3f3f3f

int MOD;

class matrix{

//为了方便操作,数据域为public
public:
//定义矩阵类型,常用的是int,long long,double
typedef int elemtype;
int row,col;
elemtype a[MAXSIZE][MAXSIZE];

public:
matrix(){}
matrix(int r,int c):row(r),col(c){}
~matrix(){}

//重新设置行列
void reset(int r,int c){ row = r; col = c; }
//将矩阵设为0矩阵
void zero(){ memset(a,0,sizeof(a)); }
//将矩阵设为1矩阵
void one(){
for(int i = 0; i < row; i++)
for(int j = 0; j < col; j++)
a[i][j] = 1;
}
//将矩阵设为单位矩阵
void identity(){
memset(a,0,sizeof(a));
for(int i = 0; i < MAXSIZE; i++) a[i][i] = 1;
}

//重载 = + - * 运算符,其中 + - * 都是取模的
//如果题目不需要取模,可以把 %MOD 去掉
//或者把 MOD 设置得很大,因为不用取模,意味着运算结果不会太大
void add_sub(const matrix &temp,matrix &now,bool isadd){
elemtype flag = isadd ? 1 : -1;
for(int i = 0; i < row; i++)
for(int j = 0; j < col; j++)
now.a[i][j] = (a[i][j]+flag*temp.a[i][j]) % MOD;
}

//保证 A.row = B.row , A.col = B.col
void operator = (const matrix &temp){
row = temp.row; col = temp.col;
for(int i = 0 ; i < row; i++)
for(int j = 0; j < col; j++)
a[i][j] = temp.a[i][j];
}

//保证 A.row = B.row , A.col = B.col
matrix operator + (const matrix &temp){
matrix now(row,col);
add_sub(temp,now,true);
return now;
}

//保证 A.row = B.row , A.col = B.col
matrix operator - (const matrix &temp){
matrix now(row,col);
add_sub(temp,now,false);
return now;
}

//保证 A.col = B.row
matrix operator * (const matrix &temp){
matrix now(row,col);
now.zero();
for(int i = 0; i < row; i++)
for(int j = 0; j < col; j++)
for(int k = 0; k < col; k++)
now.a[i][j] = (now.a[i][j] + a[i][k] * temp.a[k][j]) % MOD;
return now;
}

// 快速幂,操作的结果是保存在now中,不改变自身
matrix operator ^ (int m){
matrix now(row,col);
matrix temp = (*this);
now.identity(); //设为单位矩阵
while(m){
if(m&1) now = now * temp;
temp = temp*temp;
m /= 2;
}
return now;
}
};

matrix dfs(matrix A,int m){
if(m == 1) return A;
matrix unit(A.row,A.col);
unit.identity();
matrix S = dfs(A,m/2) * ( (A^(m/2)) + unit );
if(m&1){ S = S + (A^m); }
return S;
}

matrix solve(matrix A,int m){
return dfs(A,m);
}

int main(){
matrix A(0,0),B(0,0);
int n,m;
while(scanf("%d%d%d",&n,&m,&MOD)!=EOF){
A.reset(n,n);
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++){
scanf("%d",&A.a[i][j]);
A.a[i][j] %= MOD;
}
B = solve(A,m);
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++)
printf("%d ",B.a[i][j]);
puts("");
}
}
return 0;
}

###hdu 2855 Fibonacci Check-up
题意:略

两个预备知识

1
2
3
4
5
6
7
8
9
10
11
设fibs矩阵为 A = |1 1|
|1 0|
a[0][0] = fibs[2]
a[0][1] = a[1][0] = fibs[1]
a[1][1] = fibs[0]
这个矩阵,n次方后
a[0][0] = fibs[n+1]
a[0][1] = a[1][0] = fibs[n]
a[1][1] = fibs[n-1]
要求fibs[n]是很简单的
fib[n] = A^n (取 A[0][1] 就是 fibs[n])
1
2
二项式
(x+1)^n = c(0,n)*x^0 + c(1,n)*x^1 + c(2,n)*x^2 + ........... + c(n,n)*x^n

回到本题,要求的是

c(0,n) fibs[0] + c(1,n) fibs[1] + c(2,n) fibs[2] + ………….. + c(n,n) fibs[n]

我们抛开fibs[k]是个数字的束缚,它看做一个矩阵

c(0,n) A^0 + c(1,n) A^1 + c(2,n) A^2 + ………….. + c(n,n) A^2

这就跟二项式一样了,只不过二项式里面的x是个数字,这里是个矩阵A,不过不妨碍

原式 = (A+1)^n 1为单位矩阵

题目转化为最简单的矩阵快速幂了

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
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std;
#define LL long long
#define MAXSIZE 2
#define INF 0x3f3f3f3f

int n,MOD;

class matrix{

//为了方便操作,数据域为public
public:
//定义矩阵类型,常用的是int,long long,double
typedef int elemtype;
int row,col;
elemtype a[MAXSIZE][MAXSIZE];

public:
matrix(){}
matrix(int r,int c):row(r),col(c){}
~matrix(){}

//重新设置行列
void reset(int r,int c){ row = r; col = c; }
//将矩阵设为0矩阵
void zero(){ memset(a,0,sizeof(a)); }
//将矩阵设为1矩阵
void one(){
for(int i = 0; i < row; i++)
for(int j = 0; j < col; j++)
a[i][j] = 1;
}
//将矩阵设为单位矩阵
void identity(){
memset(a,0,sizeof(a));
for(int i = 0; i < MAXSIZE; i++) a[i][i] = 1;
}

//重载 = + - * 运算符,其中 + - * 都是取模的
//如果题目不需要取模,可以把 %MOD 去掉
//或者把 MOD 设置得很大,因为不用取模,意味着运算结果不会太大
void add_sub(const matrix &temp,matrix &now,bool isadd){
elemtype flag = isadd ? 1 : -1;
for(int i = 0; i < row; i++)
for(int j = 0; j < col; j++)
now.a[i][j] = (a[i][j] + flag * temp.a[i][j]) % MOD;
}

//保证 A.row = B.row , A.col = B.col
void operator = (const matrix &temp){
row = temp.row; col = temp.col;
for(int i = 0 ; i < row; i++)
for(int j = 0; j < col; j++)
a[i][j] = temp.a[i][j];
}

//保证 A.row = B.row , A.col = B.col
matrix operator + (const matrix &temp){
matrix now(row,col);
add_sub(temp,now,true);
return now;
}

//保证 A.row = B.row , A.col = B.col
matrix operator - (const matrix &temp){
matrix now(row,col);
add_sub(temp,now,false);
return now;
}

//保证 A.col = B.row
matrix operator * (const matrix &temp){
matrix now(row,col);
now.zero();
for(int i = 0; i < row; i++)
for(int j = 0; j < col; j++)
for(int k = 0; k < col; k++)
now.a[i][j] = (now.a[i][j] + a[i][k] * temp.a[k][j]) % MOD;
return now;
}

// 快速幂,操作的结果是保存在now中,不改变自身
matrix operator ^ (int m){
matrix now(row,col);
matrix temp = (*this);
now.identity(); //设为单位矩阵
while(m){
if(m&1) now = now * temp;
temp = temp*temp;
m /= 2;
}
return now;
}
};

int main(){
MOD = INF;
matrix A(2,2);
matrix unit(2,2);
unit.identity();
A.a[0][0] = 1; A.a[0][1] = 1;
A.a[1][0] = 1; A.a[1][1] = 0;
A = A + unit;
int T;
scanf("%d",&T);
while(T--){
scanf("%d%d",&n,&MOD);
matrix B = A ^ n;
cout << B.a[0][1] << endl;
}
return 0;
}