A6439. 「CodePlus 2018 3 月赛」博弈论与概率统计
编程题
NOI/NOI+/CTSC
知识点
题目描述
大家的好朋友小 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}$ 即可。
---
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$, $P'$，其中 $T$ 表示数据组数，$\frac{P'}{1000}$ 表示 $p$ ，即 Alice 在每轮游戏中的获胜概率。
接下来 $T$ 行，每行两个非负整数 $N,M$，表示一组数据。
输出格式
输出到标准输出。
输出 $T$ 行，每行一个整数，表示对应数据的答案。
输出 $T$ 行，每行一个整数，表示对应数据的答案。
输入输出样例
输入 #1
3 500 1 1 2 3 4 4
输出 #1
500000004 200000002 728571435
说明/提示
对于 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$ 。
<hr style='color: #ddd; margin-bottom: 1em'>
来自 CodePlus 2018 3 月赛，清华大学计算机科学与技术系学生算法与竞赛协会 荣誉出品。
Credit：idea/吕欣 命题/吕欣 验题/陈俊锟
Git Repo：https://git.thusaac.org/publish/CodePlus3
感谢腾讯公司对此次比赛的支持。
对于另外 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$ 。
<hr style='color: #ddd; margin-bottom: 1em'>
来自 CodePlus 2018 3 月赛，清华大学计算机科学与技术系学生算法与竞赛协会 荣誉出品。
Credit：idea/吕欣 命题/吕欣 验题/陈俊锟
Git Repo：https://git.thusaac.org/publish/CodePlus3
感谢腾讯公司对此次比赛的支持。