洛谷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;
}
