洛谷P5104 红包发红包 题解

题目链接：P5104 红包发红包

题意：

这个抢红包系统是这样的：假如现在有 $w$ 元，那么你抢红包能抢到的钱就是 $[0,w]$ 等概率均匀随机出的一个实数 $x$。

现在红包发了一个 $w$ 元的红包，有 $n$ 个人来抢。那么请问第 $k$ 个人期望抢到多少钱？

输出答案对 $10^9+7$ 取模后的结果。

输入格式：

一行三个整数，$w,n,k$。

输出格式：

第 $k$ 个人期望抢到的钱数对 $10^9+7$ 取模后的结果。

补充：期望可能是分数，关于分数取模，可以问度娘。

数据范围：

注意红包发明的抢红包系统和微信的抢红包系统不一样，红包发明的抢红包系统中的钱不一定是整数分。

• 对于 $30\%$ 的数据，$k=1$
• 另有 $30\%$ 的数据，期望值取模前为整数，$k\le 10$。

对于全部数据，$0< w< (10^9+7)$，$n\le 10^{18},k\le n$。

注意这道题随机出来的是实数，因此这道题是的随机变量 $X$ 是连续性随机变量。

对于连续性随机变量 $X$ ，存在一个相应的概率密度函数 $f(x)$ 。

若积分 $\int_{-\infty}^{\infty} x f(x) \mathrm{d} x$ 绝对收敛，那么 $X$ 的期望值可以计算为

$$\mathrm{E}(X)=\int_{-\infty}^{\infty} x f(x) \mathrm{d} x$$

而这道题的概率密度函数就是

$$f(x)= \begin{cases} \frac{1}{w} & 0 \leq x \leq w \\[12pt] 0 & x<0 \text { or } x>w \end{cases}$$

另外，这道题显然和 $n$ 没有任何关系，只和当前有多少人取过有关。

下面我们来证明第 $k$ 个人期望抢到 $\frac{w}{2^k}$ 。

当 $k=1$ 时，期望为

$$\int_0^w \frac{x \mathrm{~d} x}{w}=\frac{w}{2}$$

然后考虑数学归纳法，即假设 $k=n-1$ 时成立，第 $k$ 个人期望抢到

$$\int_0^w \frac{\frac{x}{2^{n-1}} \mathrm{~d} x}{w}=\frac{w}{2^n}$$

证毕。那么本题就可以光速写出来了

时间复杂度 $\mathcal{O}(\log n)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
const int mod = 1e9 + 7;
#define N ((int)())

int qpow(int a, int b)
{
    int r = 1;
    while(b) {
        if(b & 1) r = r * a % mod;
        b >>= 1; a = a * a % mod;
    }
    return r;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int w, n, k; cin >> w >> n >> k;
    int inv2 = qpow(2, mod - 2);
    cout << w * qpow(inv2, k) % mod << '\n';
    return 0;
}

---

[1] https://www.luogu.com.cn/article/1sit22ag