题解 P5104 【红包发红包】
Anguei
2018-12-16 19:52:36
首先看题：
> 抢红包能抢到的钱就是 $[0,w]$ 等概率均匀随机出的一个数 $x$。请问第 $k$ 个人期望抢到多少钱？
题目中涉及一个概念叫期望。如果您不知道什么是期望，请阅读这段文字。设一个离散型随机变量 $x$ 所有可能的取值分别为 $x_1,x_2,x_3,...,x_n$，这些值得对应概率是 $p_1,p_2,p_3,...,p_n$，则 $E(x)=x_1p_1+x_2p_2+...+x_np_n$ 叫做这个**离散型随机变量 $x$ 的均值**或**数学期望**（简称**期望**）。（摘自人教版数学课本）
通俗的讲，第 $k$ 个人期望获得的钱就是所有这个人可能获得的钱的平均值。所以：
1. 第 $1$ 个人领红包之前，剩余金额 $w$，期望领到的红包为 $\Large\frac{w}{2}$。
2. 第 $2$ 个人领红包之前，剩余金额 $\Large\frac{w}{2}$，期望领到的红包为 $\Large\frac{w}{4}$。
3. 第 $3$ 个人领红包之前，剩余金额 $\Large\frac{w}{4}$，期望领到的红包为 $\Large\frac{w}{8}$。
4. 第 $4$ 个人领红包之前，剩余金额 $\Large\frac{w}{8}$，期望领到的红包为 $\Large\frac{w}{16}$。
5. ……
所以，第 $k$ 个人期望领到的红包为 $\Large\frac{w}{2^k}$。由于需要对 $p=10^9+7$ 取模，所以答案转化为求 $w$ 与 $2^k$ 在模 $p$ 意义下的逆元的乘积。
逆元可以用快速幂求。
```cpp
const int p = 1e9 + 7.5;
int qpow(int a, int b) {
int res = 1;
while (b) {
if (b & 1) (res *= a) %= p;
(a *= a) %= p;
b >>= 1;
}
return res % p;
}
int main() {
int w = read(), n = read(), k = read();
println(w * qpow(qpow(2, k), p - 2) % p);
}
```