#1884. 冲刺

    ID: 1884 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTT赛事:contest1857来源:qoj.ac数据:公开样例动态规划概率期望

冲刺

冲刺

题目描述

标题: 冲刺 - Problem - QOJ.ac

#9642. 冲刺

Statistics

The problem was used in the following contests:

题目描述

Madeline 在登顶后下山的途中碰到了 Oshiro,他希望 Madeline 能帮他收集藏在旅馆高处的草莓。

为了方便,我们忽略旅馆的宽度,将其描述为一个 109×109 的平面。Madeline 初始位于 (0,0),有 n 个草莓,第 i 个草莓位于 (ui,vi)。由于旅馆实在太大了,Madeline 决定使用跳跃结合冲刺的办法收集草莓。假设她位于 (x,y),如果 min(x,y)<109,她将会进行如下操作:

先以 q 的概率向右跳跃,到达 (x+1,y),或 1−q 的概率向上跳跃,到达 (x,y+1)。

然后进入冲刺阶段,一次右上冲刺会使 Madeline 从 (s,t) 直接移动到 (s+1,t+1)。她会先进行一次右上冲刺。由于旅馆内有一些能量水晶,她会以 p 的概率再次进入冲刺阶段,或以 1−p 的概率退出。你可以认为 Madeline 在该阶段会以 (1−p)pi 的概率连续向右上冲刺 i+1 次(i≥0),之后结束一轮操作。

如果 Madeline 在任意时刻经过了某个草莓,则视为获得该草莓,问期望获得的草莓个数。为了方便,所有运算在 mod,P=1004535809=479×221+1 意义下进行。

输入格式

第一行输入三个整数 n,p,q。

接下来 n 行,第 i 行两个整数 ui,vi。

输出格式

输出一行一个整数表示答案。

样例

样例输入 1
3 502267905 502267905
1 0
1 2
2 2
样例输出 1
753401858

样例解释 1

可以认为 p=q=12,经过三个点的概率分别为 12,12,14。

样例 2 ~ 7

见下发文件,分别满足子任务 1,3,4,5,7,9 的限制。

数据范围

对于所有测试点,1≤n≤5000,0≤ui,vi≤107,|ui−vi|≤5000,0≤p,q<P,p≠1。

记 V=max(maxi=1nui,maxi=1nvi),b=maxi=1n|ui−vi|。

子任务编号 V≤ 特殊性质 分数 1 300 无 5 2 5000 无 5 3 107 p=0 5 4 107 q=0 5 5 5×105 b=0 5 6 107 b=0 15 7 107 b≤1 10 8 5×105 无 10 9 5×106 n≤3000 25 10 107 无 15

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

3 502267905 502267905
1 0
1 2
2 2
753401858

样例 2

990 285757264 146835319
246 220
100 52
40 232
292 169
185 91
186 140
69 171
87 270
158 273
40 27
285 203
137 134
150 70
41 273
119 93
62 79
75 134
128 225
47 174
294 200
132 44
278 148
226 223
293 137
221 3
16 159
200 192
163 47
105 162
246 142
283 219
298 293
109 140
58 189
289 75
60 279
270 20
74 20
92 141
174 116
176 55
252 78
240 43
107 169
227 61
61 55
280 299
172 6
237 176
265 229
192 217
54 95
262 296
114 94
223 25
210 154
249 152
123 244
73 291
262 135
261 250
110 253
80 57
30 262
271 116
61 153
60 268
152 49
37 86
72 164
277 248
180 237
49 287
252 8
58 104
35 202
85 208
69 237
66 6
49 240
1 99
99 190
56 76
95 198
66 123
134 10
45 40
49 173
176 274
75 277
157 114
18 4
248 100
120 51
147 69
8 250
63 170
47 36
165 106
75 74
86 209
94 272
109 261
229 18
46 58
268 297
119 241
272 183
4 74
288 94
8 267
1 12
255 121
7 294
270 164
275 35
112 272
217 5
39 262
159 18
241 192
49 195
54 64
137 218
142 80
4 139
60 69
151 294
213 146
193 175
131 142
176 165
9 30
166 214
207 205
120 190
227 119
6 267
20 272
123 97
291 50
216 49
119 122
76 246
97 108
237 47
240 63
35 283
75 170
154 4
193 169
283 139
285 37
201 257
142 246
96 246
263 229
245 260
175 245
132 29
179 149
248 238
138 248
180 103
200 123
269 281
132 181
62 137
102 196
36 203
1 37
96 230
174 56
219 55
25 170
234 181
150 150
179 93
278 269
47 235
290 281
244 64
4 108
71 212
200 64
85 1
140 88
221 211
89 174
102 3
95 245
249 101
63 268
17 232
7 255
202 233
104 32
156 181
190 57
69 150
232 148
154 73
132 281
93 167
58 12
25 105
265 182
161 136
251 130
196 282
16 70
134 276
85 3
150 186
50 132
22 81
286 207
6 135
62 195
76 223
215 165
234 2
259 153
210 19
221 154
56 10
43 237
242 247
14 93
255 113
168 226
196 90
288 90
185 129
1 224
93 36
116 1
221 122
129 218
273 69
48 211
154 7
289 111
136 8
168 163
166 109
109 91
239 92
192 296
19 24
269 48
284 149
182 256
118 223
191 83
107 34
64 37
87 268
165 264
220 160
20 293
191 208
62 129
31 17
186 266
225 219
138 159
171 221
51 277
296 6
142 122
9 56
137 188
275 61
167 257
212 147
51 30
29 150
48 183
255 99
187 39
45 85
189 297
193 5
45 122
112 41
287 146
218 108
234 292
234 274
107 42
163 118
37 111
221 180
256 83
96 181
279 123
6 38
192 188
276 238
205 93
162 250
113 199
42 83
163 149
60 272
252 43
160 170
106 163
125 201
51 9
6 167
268 121
77 97
143 56
34 257
199 39
171 67
160 26
78 53
80 153
283 186
295 19
164 93
248 45
286 1
296 28
74 115
177 134
244 153
245 19
269 193
108 262
273 73
1 39
173 280
68 288
199 288
204 3
83 134
8 107
289 245
166 193
189 36
218 78
51 111
80 148
7 81
164 217
29 63
85 290
15 197
273 266
34 154
67 69
162 3
30 182
281 155
157 116
116 139
106 130
220 164
265 130
7 238
235 120
48 32
31 225
77 84
23 291
196 141
11 241
71 196
198 82
228 297
255 102
50 75
122 95
151 171
59 46
227 64
231 174
78 105
255 118
2 62
90 103
176 170
124 225
111 266
287 138
267 37
106 164
83 174
273 160
128 94
261 171
8 221
183 46
101 39
291 298
156 116
28 293
224 144
192 197
40 68
116 125
204 69
100 183
145 0
6 1
110 165
98 124
229 255
291 258
211 255
243 201
255 246
69 127
299 195
198 175
76 286
40 270
246 12
65 226
266 60
72 197
8 0
186 276
19 125
70 264
236 188
90 283
82 289
233 262
0 68
28 34
130 124
30 50
171 255
282 51
102 140
241 38
13 153
270 81
98 111
165 230
106 39
270 70
209 115
233 278
44 60
138 187
295 46
128 144
180 109
157 53
99 228
194 105
147 222
243 251
265 223
166 61
256 196
120 103
232 203
290 30
95 256
35 209
249 190
229 113
106 261
3 56
13 227
175 242
276 184
159 270
80 190
222 226
290 208
270 86
274 118
56 221
88 220
225 141
53 56
161 278
230 95
129 25
93 29
184 255
39 2
193 240
229 88
165 260
232 144
99 258
277 108
4 39
246 0
176 259
1 139
238 161
105 190
48 246
138 175
102 75
199 106
120 104
223 272
37 183
113 102
292 136
133 287
279 221
50 191
163 223
220 262
264 258
18 274
26 271
137 78
288 7
130 108
148 2
231 206
30 129
211 109
156 95
56 51
153 281
116 251
120 182
100 162
152 103
0 61
256 117
162 297
20 95
34 18
258 222
169 166
167 50
96 54
224 286
43 180
60 218
234 83
179 58
294 290
144 289
183 115
250 12
29 136
6 200
286 91
273 251
185 57
102 44
67 8
7 65
171 248
192 85
56 259
163 144
26 163
87 126
110 251
291 161
104 58
211 76
70 23
103 185
268 19
88 48
56 146
125 84
239 250
291 10
170 0
137 109
43 111
254 9
55 203
235 173
3 239
66 1
136 9
229 116
174 140
219 122
282 47
207 211
76 230
45 187
177 38
212 159
212 212
289 128
19 222
48 223
92 156
64 154
42 226
171 51
270 94
179 13
278 109
116 46
79 283
159 188
168 271
120 96
130 293
110 254
134 61
116 83
291 55
59 264
15 56
113 173
5 288
146 84
29 285
132 238
135 156
230 280
89 227
223 161
140 83
211 295
32 216
154 118
144 251
40 110
261 216
122 8
185 125
24 204
193 79
82 116
114 3
8 30
1 288
65 243
30 220
20 121
205 98
143 214
178 37
195 3
246 89
57 227
149 20
214 128
270 182
220 298
8 40
283 292
144 61
195 17
180 73
298 221
66 37
127 203
260 49
118 259
222 147
178 92
298 66
47 43
276 259
202 159
144 162
135 223
249 194
96 58
48 230
187 82
77 234
208 50
175 209
257 289
272 256
59 149
111 210
129 13
123 111
24 287
106 264
225 203
138 178
296 258
7 153
134 284
114 185
28 222
268 11
169 65
62 223
242 198
220 296
275 151
228 264
35 147
179 53
188 23
290 60
277 10
40 171
139 175
266 298
178 105
16 71
170 28
115 46
198 246
94 21
275 171
234 108
254 98
201 84
261 46
213 278
205 113
15 149
182 284
294 56
187 87
10 162
233 210
282 84
266 21
207 3
101 234
226 75
206 68
286 123
269 135
73 24
2 149
25 48
47 277
284 255
42 154
55 97
197 231
208 163
226 73
215 122
246 148
152 90
56 228
13 212
269 259
178 190
71 64
293 97
44 99
74 10
243 101
139 268
10 27
2 216
231 120
172 152
80 159
103 279
159 147
167 132
39 130
266 7
29 286
11 98
294 186
141 244
79 61
83 183
244 230
154 2
77 78
296 201
222 18
266 90
182 254
64 216
189 195
144 44
97 0
138 3
51 7
5 292
298 214
88 151
34 62
203 177
287 21
165 171
198 99
48 218
13 92
20 120
116 0
182 100
135 274
187 232
75 91
123 132
192 83
166 49
174 121
287 0
157 151
180 201
102 277
266 171
149 290
271 10
155 272
148 200
214 177
230 82
112 129
273 273
264 197
43 101
188 124
81 190
272 294
68 206
220 170
202 171
172 95
143 11
51 234
245 63
293 183
233 87
83 33
152 185
278 241
131 265
279 200
291 254
58 112
284 161
207 146
55 239
6 284
287 252
126 141
123 41
210 153
93 185
95 142
204 108
63 42
254 67
204 103
236 186
256 208
12 163
127 104
171 108
40 118
224 282
147 295
64 2
298 107
221 54
97 188
78 78
22 94
206 74
291 129
41 177
80 31
239 111
214 72
145 217
297 7
286 36
6 210
67 203
200 230
172 145
96 277
249 91
30 44
105 208
11 107
95 289
21 63
31 50
126 47
101 79
206 161
81 53
31 106
94 178
31 111
102 0
116 10
134 45
207 261
178 165
96 55
153 250
195 53
74 87
194 238
266 128
144 63
113 223
105 170
6 95
72 243
1 77
227 142
291 53
267 112
159 279
218 36
142 281
265 179
242 196
222 63
233 75
155 113
157 251
194 15
295 209
178 151
45 32
180 93
58 58
60 194
24 176
120 34
140 191
187 134
222 161
48 264
103 214
168 234
129 56
95 166
0 225
266 161
40 75
45 129
93 150
203 126
228 126
210 171
182 219
21 20
87 298
135 37
72 17
149 204
43 18
137 252
128 5
162 191
57 126
16 75
14 20
96 284
285 209
57 148
95 238
50 22
243 113
244 81
261 30
96 12
119 91
173 173
78 171
4 267
294 252
6 138
5 194
298 230
148 220
158 73
127 233
22 231
197 295
236 274
98 109
428692098