#6300. 「CodePlus 2018 3 月赛」博弈论与概率统计

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

大家的好朋友小 L 来到了博弈的世界。


Alice 和 Bob 在玩一个双人游戏。每一轮中,Alice 有 p 的概率胜利, 1-p 的概率失败,不会出现平局。

双方初始时各有 0 分,当一个人胜利的时候,他会获得一分,失败则扣掉一分。遗憾的是,博弈论世界的人目前是无法理解负数的,因此,如果某个人输掉一轮比赛的时候他只有 0 分,那么他就不会被扣分(对方会照常加一分)。游戏一共要进行 N+M 轮,Alice 想请你帮她算算在游戏结束时她的得分的数学期望。

“这算啥,我小 L 分分钟搞定!”。比小 L 更熟练的你当然也是随手就算出来了,但就在你打算告诉 Alice 答案之前,博弈论世界之神——temporaryDO 出现了,他给大家带来了一个重要信息:这 N+M 轮游戏中, Alice 恰好赢了 N 轮!

熟知条件概率那套理论的你立刻注意到,你需要修改自己的计算方法来得到正确的答案了。

为了避免精度问题,请将结果对 10^9+7 取模。即,我们的数据保证答案是一个有理数 \frac{p}{q} ,且有 10^9+7\nmid q ,你只需要找到一个整数 x\in [0, 10^9+7) 使得 qx\equiv p\pmod{10^9+7} 即可。

输入格式

从标准输入读入数据。

输入的第一行包含两个正整数 T , P' ,其中 T 表示数据组数, \frac{P'}{1000} 表示 p ,即 Alice 在每轮游戏中的获胜概率。

接下来 T 行,每行两个非负整数 N,M ,表示一组数据。

输出格式

输出到标准输出。

输出 T 行,每行一个整数,表示对应数据的答案。

样例

样例 1 输入

3 500
1 1
2 3
4 4

样例 1 输出

500000004
200000002
728571435

样例 1 解释

每一轮游戏 Alice 均有 \frac{1}{2} 的概率胜利。

  • 对于第一组数据,Alice 的胜利可能在第一轮或第二轮,并且概率相等。若她在第一轮胜利,则最终得分为 0 ,否则她的得分为 1 。故期望为 \frac{1}{2} ,验证发现 2\times 500000004\equiv 1\pmod{10^9+7}
  • 对于第二组数据,所求期望为 \cfrac{3}{5}
  • 对于第三组数据,所求期望为 \cfrac{93}{70}

样例 2

见附加文件的 2.in2.ans

数据范围与提示

对于 10% 的数据, N,M,T\le 50
对于另外 20% 的数据, N,M,T\le 2000
对于另外 20% 的数据, N,M\le 10^5 |N-M|\le 200 T\le 2\times 10^5
对于另外 20% 的数据, N,M,T\le 5\times 10^4
对于 100% 的数据, N+M,T\le 2.5\times 10^5 0 < P' < 1000


来自 CodePlus 2018 3 月赛,清华大学计算机科学与技术系学生算法与竞赛协会 荣誉出品。
Credit:idea/吕欣 命题/吕欣 验题/陈俊锟
Git Repo:https://git.thusaac.org/publish/CodePlus3
感谢腾讯公司对此次比赛的支持。