1. 问题背景与理解
今天我们来拆解一道有趣的概率期望题目——P5104红包发红包。这道题源自信息学竞赛题库，考察了对概率期望的理解和模运算的应用。题目描述了一个简化的抢红包系统：总金额为w元的红包被n个人依次抢走，每个人抢到的金额是在[0,当前剩余金额]区间内均匀分布的随机实数。我们需要计算第k个人期望抢到的金额，并对结果取模。
注意：这里的"红包"系统与日常使用的微信红包不同，金额可以是任意实数而非固定份额。
2. 问题分析与数学推导
2.1 基础概率模型
首先考虑最简单的情况：只有1个人(k=1)抢红包。此时期望值显然是w/2，因为金额在[0,w]均匀分布。
当有n个人时，情况变得复杂。第k个人的期望金额需要考虑前面k-1个人已经抢走部分金额的影响。经过数学推导（详见后文），我们可以得到一个惊人的结论：第k个人的期望金额与总人数n无关！
2.2 递推关系建立
设E(k)为第k个人的期望金额。我们可以建立如下递推关系：
- 第1个人的期望：E(1) = w/2
- 第2个人抢时，剩余金额期望为w - E(1) = w/2
所以E(2) = (w/2)/2 = w/4 - 第3个人抢时，剩余金额期望为w - E(1) - E(2) = w/4
所以E(3) = (w/4)/2 = w/8
由此可归纳出一般规律：E(k) = w/(2^k)
2.3 模运算处理
由于题目要求对1e9+7取模，且期望可能是分数，我们需要处理分数取模的问题。在模数p为质数时，a/b mod p等价于a*b^(p-2) mod p（费马小定理）。
因此，w/(2^k) mod 1e9+7可以转化为：
w * pow(2, k*(1e9+7-2)) mod 1e9+7
3. C++代码实现解析
3.1 快速幂实现
cpp复制typedef long long LL;
const int ha=1e9+7;
LL Pow(LL a,LL b) {
LL ans=1;
for(;b;b>>=1,a=a*a%ha)
if(b&1) ans=ans*a%ha;
return ans;
}
这个快速幂函数实现了O(logb)时间复杂度的模幂计算，使用了二进制分解的思想：
- 每次将指数b右移一位
- 根据当前最低位决定是否乘入结果
- 底数a不断平方
3.2 主逻辑实现
cpp复制int main() {
cin>>w>>n>>k;
LL inv2=Pow(2,ha-2); // 计算2的模逆元
LL ans=w*Pow(inv2,k)%ha; // w/(2^k) mod ha
cout<<ans<<endl;
return 0;
}
关键点：
- 计算2的模逆元inv2 = 2^(ha-2) mod ha
- 1/(2^k) mod ha = (inv2)^k mod ha
- 最终结果 = w * (inv2)^k mod ha
4. 算法优化与注意事项
4.1 时间复杂度分析
- 快速幂时间复杂度：O(log(p))，这里p=1e9+7，约30次迭代
- 整体复杂度：O(log(k) + log(p)) ≈ O(1) 对于k≤1e18
4.2 边界情况处理
- w=0时：虽然题目保证w>0，但实际应用中应检查
- k=0时：题目保证k≥1，但健壮代码可添加判断
- 大数相乘：使用long long防止溢出，必要时可改用__int128
4.3 常见错误
- 忘记取模：每次乘法后都应取模
- 模逆元计算错误：确保模数是质数（1e9+7是质数）
- 整数溢出：使用足够大的数据类型（如long long）
5. 数学证明与深入理解
5.1 严格数学证明
设第i个人抢到的金额为X_i，剩余金额S_i = w - ΣX_j (j=1..i)
由题意，X_i ~ Uniform(0, S_{i-1})
E[X_i] = E[E[X_i|S_{i-1}]] = E[S_{i-1}/2] = E[S_{i-1}]/2
又因为E[S_i] = E[S_{i-1} - X_i] = E[S_{i-1}]/2
递推可得：
E[S_i] = w/(2^i)
E[X_i] = w/(2^i)
5.2 与真实红包系统的对比
真实红包系统（如微信）通常：
- 使用固定金额分割
- 有最小金额限制
- 可能采用不同的分布策略
相比之下，本题模型更简单，便于数学分析。
6. 扩展思考与变种问题
6.1 变种问题1：固定总额
如果总金额固定为w，n个人抢完后金额必须用完，期望如何变化？
6.2 变种问题2：不同分布
如果抢到的金额不是均匀分布，而是正态分布或其他分布，如何计算？
6.3 实际应用
类似模型可用于：
- 资源分配问题
- 带宽共享
- 任务调度
7. 竞赛技巧与训练建议
- 概率期望题的关键是找到递推关系
- 模运算要熟练掌握费马小定理
- 快速幂是基础算法，必须熟练实现
- 测试边界条件：k=1, k=n, w接近1e9+7等
8. 代码测试与验证
测试用例设计：
cpp复制void test() {
assert(solve(2,1,1) == 1); // 样例
assert(solve(100,2,1) == 50);
assert(solve(100,2,2) == 25);
assert(solve(1e9+6,1e18,1) == (1e9+6)/2 % (1e9+7));
}
9. 性能优化进阶
对于极端大的k（如1e18），可以进一步优化：
- 预处理常用幂次
- 使用更快的幂函数（如查表法）
- 并行计算（对于多个查询）
10. 总结与个人心得
这道题看似简单，但融合了多个重要知识点：
- 概率期望的计算
- 递推关系的建立
- 模运算与费马小定理
- 快速幂算法
在实际编码中，我发现几个易错点：
- 模数1e9+7不要写成10e9+7
- 快速幂的终止条件要写对
- 中间结果可能溢出，要及时取模
建议初学者可以：
- 先手算小例子验证理解
- 分步骤实现（先写快速幂，再处理主逻辑）
- 添加详细的注释帮助理解
通过这道题，我对概率期望在程序设计中的应用有了更深的理解。后续可以继续研究更复杂的概率模型和其在实际问题中的应用。