HDU 4887 Endless Punishment (矩阵+BSGS)

HDU 4887

Endless Punishment

Endless Punishment

Time Limit: 30000/15000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 95 Accepted Submission(s): 41

Problem Description

In the ancient Greek tale, Sisyphus was a king of Ephyra, he was punished for chronic deceitfulness by being compelled to roll an immense stone up a hill every day, only to watch it roll back down, and to repeat this action forever. Zeus, the God of the universe, shows some mercy for Sisyphus, so he decides to change the way of punishment. He puts N stones with the color of white or black in a line on the hill, everyday when Sisyphus rolls a new stone up the hill, the new stone is added to the back of the old N stones, and the first stone rolls down to the foot of the hill. Then Zeus shows his magic to change the color of the new N stones. Firstly, he looks at a subset S1 of the original N stones, which always includes the first stone, if an odd number of the stones are black, then the newly N-th stone will be black and white otherwise. After the first step is done, he flips the color of another subset S2 of the new N stones, black stone will become white, and white stone will become black vice versa. The following example illustrates how Zeus’s magic works. Consider the case of N = 4, S1 = {1,3}, S2 = {2,4}. Suppose the current stone color state is ●○○○, (○ for white stone, and ● for black stone), the 1st and 3rd stone is black and white respectively, so the new 4th stone will be black, produces ○○○● after the first step. At the second step, the 2nd and 4th stone flip its color, produces ○●○○ in the end. Zeus tells to Sisyphus that, if one day after the two steps are done, the color of the stones turns to one specific state, he will get his freedom. Now given the current and final stone colors, please compute how many days are needed for Sisyphus’s freedom?

Input

There are several test cases, please process till EOF. For each test case, the first line contains three integers, the first integer is N(2 ≤ N ≤ 31), the number of stones, followed by two integers S1 and S2, (1 ≤ S1,S2 ≤ N), denoting the size of two subsets as mentioned above. The second and third line contains S1 and S2 integers a and b in the increasing order, describing the two subsets. It is guaranteed that a1 always equals to 1. The last two lines each contains N integers with 0 (for white), or 1 (for black) denoting the current and final state. The first integer describes the first stone, and the last integer describes the last stone. Please note that there are about 500 test cases, fortunately, only 20 of them are big test cases.

Output

For each test case, output a single integer, the minimum days for Sisyphus to get his freedom. If Zeus is an absolute liar, then just simply print the sentence poor sisyphus.

Sample Input

4 2 2 1 3 2 4 1 0 0 0 0 1 0 0 4 2 2 1 3 2 4 1 1 1 1 0 0 0 0 4 2 2 1 3 2 4 1 1 1 1 0 1 0 0 10 5 6 1 2 4 5 6 2 4 5 8 9 10 0 0 0 0 0 0 1 0 0 0 1 1 1 1 1 1 1 1 1 1

Sample Output

1 4 poor sisyphus 387

Author

Fudan University

Source

2014 Multi-University Training Contest 3

题意很清楚。N(2 ≤ N ≤ 31)个01串,按照规则去变化,问经过几步可以从原串变化到目标串。

首先需要说明的是,两个变化其实都可以写成矩阵形式,运算就是异或,也就是模2加。 把N个01向量,后面加一个1,变成N+1维,这样两个操作都可以使用N+1 * N+1 的矩形进行表示了。 然后还有个问题,因为S1集合里面一定包含了1, 所以这两个操作都是可逆的。 使用BSGS的方法去寻找。 状态最多是 1<<n step = ceil(sqrt(1<<n)). 首先从目标态,倒着求step步的状态,进行映射。 这个就是baby step. 然后从初始状态,每次走大步, 知道落入刚才的映射值。 小步的时候,复杂度是O(n), 大步的时候复杂度是O(n^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
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
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
/* ***************

Author :kuangbin

Created Time :2014/8/3 9:31:49

File Name :E:\2014ACM\比赛\2014多校训练\2014多校3\HDU4887.cpp

************************************************ */

#include <stdio.h>

#include <string.h>

#include <iostream>

#include <algorithm>

#include <vector>

#include <queue>

#include <set>

#include <map>

#include <string>

#include <math.h>

#include <stdlib.h>

#include <time.h>

using namespace std;

//矩阵

struct Matrix

{

int n;

int mat[40][40];

void init(int _n)

{

n = _n;

memset(mat,0,sizeof(mat));

}

Matrix operator *(const Matrix &b)const

{

Matrix ret;

ret.init(n);

for(int i = 0;i < n;i++)

for(int j = 0;j < n;j++)

{

for(int k = 0;k < n;k++)

{

ret.mat[i][j] += (mat[i][k]*b.mat[k][j])&1;

ret.mat[i][j] &= 1;

}

}

return ret;

}

void debug()

{

printf("n : %d\n",n);

for(int i = 0;i < n;i++)

{

for(int j = 0;j < n;j++)printf("%d ",mat[i][j]);

cout<<endl;

}

}

};

Matrix pow_M(Matrix a,int n)

{

Matrix ret;

ret.init(a.n);

for(int i = 0;i < a.n;i++)ret.mat[i][i] = 1;

Matrix tmp = a;

while(n)

{

if(n&1)ret = ret*tmp;

tmp = tmp*tmp;

n >>= 1;

}

return ret;

}

Matrix A,B,C,D;

int a[40],b[40],c[40],d[40];

int main()

{

//freopen("in.txt","r",stdin);

//freopen("out.txt","w",stdout);

int n;

int S1,S2;

while(scanf("%d%d%d",&n,&S1,&S2) == 3)

{

A.init(n+1);//第一个操作的变换矩阵

for(int i = 0;i < n-1;i++)A.mat[i+1][i] = 1;

A.mat[n][n] = 1;

for(int i = 0;i < S1;i++)

{

scanf("%d",&a[i]);

a[i]--;

A.mat[a[i]][n-1] = 1;

}

int change = 0;

B.init(n+1);//第二个操作矩阵

for(int i = 0;i < n+1;i++)B.mat[i][i] = 1;

for(int i = 0;i < S2;i++)

{

scanf("%d",&b[i]);

b[i]--;

change |= (1<<(n-1-b[i]));

B.mat[n][b[i]] = 1;

}

for(int i = 0;i < n;i++)scanf("%d",&c[i]);

int end = 0;

for(int i = 0;i < n;i++)

{

scanf("%d",&d[i]);

end <<= 1;

end |= d[i];

}

int step = ceil(sqrt((1LL)<<n));

map<int,int>mp;

int now = end;

for(int i = 0;i < step;i++)

{

if(mp.find(now) == mp.end())mp[now] = i;

else break;

now ^= change;

int tmp = now&1;

for(int j = 1;j < S1;j++)

tmp ^= ( (now&(1<<(n-1-(a[j]-1)))) != 0 );

now >>= 1;

now |= tmp*(1<<(n-1));

}

int tot = (1LL<<n)/step;

int ans = -1;

//A.debug();

//B.debug();

C = A*B;

C = pow_M(C,step);

c[n] = 1;

for(int i = 0;i <= tot;i++)

{

int st = 0;

for(int j = 0;j < n;j++)

{

st <<= 1;

st |= c[j];

}

if(mp.find(st) != mp.end())

{

ans = i*step + mp[st];

break;

}

for(int j = 0;j <= n;j++)

{

d[j] = 0;

for(int k = 0;k <= n;k++)

{

d[j] ^= ((c[k]*C.mat[k][j])&1);

}

}

for(int j = 0;j <= n;j++)c[j] = d[j];

}

if(ans == -1)printf("poor sisyphus\n");

else printf("%d\n",ans);

}

return 0;

}
------ 本文结束------
  • 本文作者: kuangbin
  • 本文链接: 306.html
  • 版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明出处!
0%