廷哥带你小路超车1. 问题背景与数学原理拆解
今天遇到一个有趣的概率期望问题，来自洛谷P5104的"红包发红包"题目。题目描述了一个抢红包系统：总金额为w元，n个人依次抢红包，每个人抢到的金额是在[0,当前剩余金额]区间内均匀分布的随机实数。我们需要计算第k个人期望抢到的金额，并对1e9+7取模。
这个问题的核心在于理解两个关键数学概念：期望值的计算和模运算下的除法处理。让我先解释一下背后的数学原理：
在概率论中，均匀分布是最基础的概率分布之一。对于一个在[0,x]区间内均匀分布的随机变量，它的期望值就是区间的中点x/2。这个性质很好理解——如果无数个人来抢这个红包，长期平均下来每个人抢到的金额就是当前金额的一半。
但问题来了：当第k个人抢红包时，前面的k-1个人已经抢过一轮了。根据期望的线性性质，我们可以推导出第k个人的期望金额应该是w/(2^k)。这个推导过程很有意思：
- 第1个人的期望：w/2
- 第2个人抢时，剩余金额的期望是w/2，所以他的期望是(w/2)/2 = w/4
- 以此类推，第k个人的期望就是w/(2^k)
需要模型API调用？ 免费领10W Token，多模型网关一键接入 Claude、DeepSeek 等主流模型。
2. 模运算与费马小定理的应用
题目要求我们对结果取模1e9+7（这是一个质数）。在模运算中，除法不能直接进行，需要转换为乘以模逆元。这就是费马小定理大显身手的地方了。
费马小定理告诉我们：对于一个质数p和不是p的倍数的整数a，有a^(p-1) ≡ 1 (mod p)。这意味着a的逆元就是a^(p-2)，因为a × a^(p-2) ≡ 1 (mod p)。
在我们的题目中，需要计算w/(2^k) mod 1e9+7，这等价于w × (2^k)^(-1) mod 1e9+7。根据费马小定理，(2^k)^(-1) ≡ (2^k)^(1e9+7-2) ≡ pow(2, k*(1e9+7-2)) mod 1e9+7。
3. 快速幂算法实现
为了高效计算大指数的模运算，我们需要使用快速幂算法。快速幂通过二分思想将O(n)的复杂度降为O(log n)，这对于n可能高达1e18的情况至关重要。
快速幂的基本思想是：
- 将指数表示为二进制形式
- 利用平方的性质：a^b = (a^(b/2))^2（如果b是偶数）
- 或者a^b = a × (a^((b-1)/2))^2（如果b是奇数）
cpp复制typedef lon