矩阵题目

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

hdu 3306 Another kind of Fibonacci

转化一下公式吧

构造一个矩阵 ( si-1,Ai^2 , Ai-1 ^ 2) , 得到 (si , Ai+1 ^ 2 , Ai^2)

Ai + 1 = X Ai + Y Ai - 1 , Ai + 1^2 = X^2 Ai^2 + Y^2 Ai^2 + 2 X Y Ai Ai - 1

多了 Ai * Ai-1 这个项,所以就往矩阵里面加点东西吧…

( si-1,Ai^2 , Ai-1 ^ 2 , Ai Ai-1) ——> (si , Ai+1 ^ 2 , Ai^2 , Ai+1 Ai)

看看Ai+1 Ai , Ai+1 Ai = (X Ai + Y Ai-1) Ai = X Ai^2 + Y Ai Ai-1

这样就有Ai*Ai-1了

1
2
3
4
5
构造矩阵
1 0 0 0
1 X^2 1 X
0 Y^2 0 0
0 2XY 0 Y
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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std;
#define LL long long
#define MOD 10007
#define MAXSIZE 4

class matrix{

//为了方便操作,数据域为public
public:
//定义矩阵类型,常用的是int,long long,double
typedef long long 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) % 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) % 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;
}
void show(){
for(int i = 0 ; i < row; i++){
for(int j = 0; j < col; j++)
printf("%d ",a[i][j]);
puts("");
}
}
};

matrix A,M,B;

int main(){
A.reset(1,4);
M.reset(4,4);
A.a[0][0] = 1; A.a[0][1] = 1; A.a[0][2] = 1; A.a[0][3] = 1;
LL n,x,y;
while(cin >> n >> x >> y){
M.a[0][0] = 1; M.a[0][1] = 0; M.a[0][2] = 0; M.a[0][3] = 0;
M.a[1][0] = 1; M.a[1][1] = (x*x)%MOD; M.a[1][2] = 1; M.a[1][3] = x%MOD;
M.a[2][0] = 0; M.a[2][1] = (y*y)%MOD; M.a[2][2] = 0; M.a[2][3] = 0;
M.a[3][0] = 0; M.a[3][1] = (2*x*y)%MOD; M.a[3][2] = 0; M.a[3][3] = y%MOD;

if(n == 0) puts("0");
else{
B = (A * (M ^ (n-1)));
cout << (B.a[0][0]+B.a[0][1])%MOD << endl;
}
}
return 0;
}

hdu 1588 Gauss Fibonacci

这题的话,挺好的,其实有之前两道矩阵题的结合

fibs矩阵(简称A)

1
2
1 1
1 0

它的幂次就是对应的fibs项

所以f(g(i))统一用fibs矩阵表示

1
2
3
4
5
f(g0) = f(b) = A^b
f(g1) = f(k+b) = A ^ (k+b)
f(g2) = f(2k+b) = A ^ (2k+b)
......
f(gn-1) = f(k(n-1)+b) = A ^ (k(n-1)+b)

求和,那么首先把A^b提出来,剩下A^k + A^2k + A^3K …………………

把A^k单独看为B,变为B + B^2 + B^3 + B^4 + ……………….

这就变成了 poj 3233 Matrix Power Series 可以两种方法做

另外,考虑一下b = 0,k = 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
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
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
#define LL long long
#define MAXSIZE 4

LL MOD;

class matrix{

//为了方便操作,数据域为public
public:
//定义矩阵类型,常用的是int,long long,double
typedef LL 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) % 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) % 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;
}
void show(){
for(int i = 0 ; i < row; i++){
for(int j = 0; j < col; j++)
printf("%d ",a[i][j]);
puts("");
}
}
};

matrix A,B,Ab,L,MID,R;

void solve(LL k,LL b,LL n){
B = (A ^ (int)k);
//B.show();
L.reset(2,4);
for(int i = 0; i < 2; i++)
for(int j = 0; j < 2; j++){
L.a[i][j] = 0LL;
L.a[i][j+2] = B.a[i][j];
}
MID.reset(4,4);
for(int i = 0 ; i < 2; i++)
for(int j = 0; j < 2; j++){
MID.a[i][j] = i == j ? 1LL : 0LL;
MID.a[i+2][j] = i == j ? 1LL : 0LL;
MID.a[i][j+2] = 0;
MID.a[i+2][j+2] = B.a[i][j];
}
//(MID ^ (n-1)).show();
R = L * (MID ^ (n-1));
//R.show();
matrix unit(2,2);
unit.identity();
R = R + unit;
}

int main(){
LL k,b,n;
while(cin >> k >> b >> n >> MOD){
A.reset(2,2);
A.a[0][0] = 1LL; A.a[0][1] = 1LL;
A.a[1][0] = 1LL; A.a[1][1] = 0LL;
if(b == 0LL){
if(k == 0LL) puts("0");
else{
// B = A^k
// A^k + A^2k + A^3k ..... + A^(n-1)k
// B + B^2 + B^3 + ...... + B^(n-1)
solve(k,b,n);
cout << R.a[0][1] << endl;
}
}
else{
Ab = (A ^ (int)b);
if(k == 0LL){ cout << (A.a[0][1]*n)%MOD << endl; }
else{
// B = A^k
// A^b * (I + B + B^2 + B^3 .... + B^(n-1))
solve(k,b,n);
R = R * Ab;
cout << R.a[0][1] << endl;
}
}
}
return 0;
}