#PQJ1857x9642. QOJ 1857_9642
QOJ 1857_9642
标题: 冲刺 - Problem - QOJ.ac
#9642. 冲刺
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