题解 | #抢红包#

题目链接

抢红包

题目描述

一个红包总金额为 $W$ 元，有 $N$ 个人来抢。规则如下：如果红包里还剩 $w$ 元，下一个人抢到的金额是从区间 $[0, w]$ 中等概率均匀随机出的一个实数。

求第 $K$ 个人期望抢到多少钱，结果对 $10^9 + 7$ 取模。

输入:

输入一行，包含三个整数 $W, N, K$ 。

输出:

输出一行，表示第 $K$ 个人期望抢到的钱数对 $10^9 + 7$ 取模后的结果。

解题思路

这是一个经典的期望问题，可以通过线性递推来解决。

1. 定义状态

设 $X_i$ 为第 $i$ 个人抢到的金额（一个随机变量）。
设 $W_i$ 为第 $i$ 个人抢红包之前，红包里剩余的金额（也是一个随机变量）。
我们要求的是第 $K$ 个人的期望金额，即 $E[X_K]$ 。

2. 分析单次期望

根据题目规则，如果红包里有 $w$ 元，抢到的金额是 $[0, w]$ 上的均匀分布。一个在 $[a, b]$ 上均匀分布的随机变量，其期望值为 $(a+b)/2$ 。
因此，在已知红包剩余 $W_i=w_i$ 的情况下，第 $i$ 个人抢到金额的条件期望是 $E[X_i | W_i=w_i] = (0+w_i)/2 = w_i/2$ 。

3. 建立递推关系

根据全期望公式， $E[X_i] = E[E[X_i | W_i]] = E[W_i/2] = E[W_i]/2$ 。
这说明，第 $i$ 个人的期望金额是抢红包前剩余金额的期望值的一半。
接下来，我们分析剩余金额期望 $E[W_i]$ 的关系。第 $i+1$ 个人抢之前剩余的钱 $W_{i+1}$ ，等于第 $i$ 个人抢之前剩余的钱 $W_i$ 减去第 $i$ 个人抢走的钱 $X_i$ 。即 $W_{i+1} = W_i - X_i$ 。
两边取期望，利用期望的线性性质，得到 $E[W_{i+1}] = E[W_i - X_i] = E[W_i] - E[X_i]$ 。
将 $E[X_i] = E[W_i]/2$ 代入，得到 $E[W_{i+1}] = E[W_i] - E[W_i]/2 = E[W_i]/2$ 。

4. 求解通项公式

我们得到了一个关于剩余金额期望的递推式： $E[W_{i+1}] = E[W_i]/2$ 。
初始条件是 $E[W_1] = W$ （第一个人抢之前，红包里有全部金额）。
这是一个等比数列，可以得到通项公式： $E[W_i] = W / 2^{i-1}$ 。
因此，第 $K$ 个人抢到金额的期望为 $E[X_K] = E[W_K]/2 = (W / 2^{K-1}) / 2 = W / 2^K$ 。

5. 计算结果

我们需要计算 $(W / 2^K) \pmod{10^9 + 7}$ 。
这等价于计算 $(W \cdot (2^K)^{-1}) \pmod{10^9 + 7}$ 。
模数 $10^9+7$ 是一个质数，我们可以使用费马小定理来求乘法逆元。对于质数模 $p$ ， $a^{p-2} \equiv a^{-1} \pmod p$ 。
一个高效的计算方法是先求出 $2$ 的逆元 inv2，然后计算 inv2 的 $K$ 次方。
inv2 $= 2^{p-2} \pmod p$ 。
最终结果是 $(W \cdot \text{inv2}^K) \pmod p$ 。
所有幂运算都可以通过快速幂来高效完成。

代码

c++
java
python

#include <iostream>

using namespace std;

typedef long long LL;

LL power(LL base, LL exp) {
    LL res = 1;
    LL mod = 1e9 + 7;
    base %= mod;
    while (exp > 0) {
        if (exp % 2 == 1) res = res * base % mod;
        base = base * base % mod;
        exp /= 2;
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    LL w, n, k;
    cin >> w >> n >> k;

    LL mod = 1e9 + 7;
    
    // 计算 2 的乘法逆元
    LL inv2 = power(2, mod - 2);
    
    // 计算 2^k 的乘法逆元，即 (2的逆元)^k
    LL inv2_k = power(inv2, k);
    
    // 期望 = W * (1/2^k)
    LL ans = (w * inv2_k) % mod;
    
    cout << ans << endl;

    return 0;
}

import java.util.Scanner;

public class Main {
    static long power(long base, long exp) {
        long res = 1;
        long mod = 1_000_000_007;
        base %= mod;
        while (exp > 0) {
            if (exp % 2 == 1) res = (res * base) % mod;
            base = (base * base) % mod;
            exp /= 2;
        }
        return res;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long w = sc.nextLong();
        long n = sc.nextLong();
        long k = sc.nextLong();

        long mod = 1_000_000_007;

        // 计算 2 的乘法逆元
        long inv2 = power(2, mod - 2);

        // 计算 2^k 的乘法逆元，即 (2的逆元)^k
        long inv2_k = power(inv2, k);

        // 期望 = W * (1/2^k)
        long ans = (w * inv2_k) % mod;

        System.out.println(ans);
    }
}

import sys

def power(base, exp):
    res = 1
    mod = 10**9 + 7
    base %= mod
    while exp > 0:
        if exp % 2 == 1:
            res = (res * base) % mod
        base = (base * base) % mod
        exp //= 2
    return res

def main():
    w, n, k = map(int, sys.stdin.readline().split())
    mod = 10**9 + 7
    
    # 计算 2 的乘法逆元
    inv2 = power(2, mod - 2)
    
    # 计算 (1/2)^k
    inv2_k = power(inv2, k)
    
    # 期望 = W * (1/2^k)
    ans = (w * inv2_k) % mod
    
    print(ans)

if __name__ == "__main__":
    main()

算法及复杂度

算法：数学期望 + 快速幂求逆元
时间复杂度：算法主要由两次快速幂运算构成。一次用于求 $2$ 的逆元，其指数为 $MOD-2$ ；另一次用于求逆元的 $K$ 次方。总时间复杂度为 $\mathcal{O}(\log{MOD} + \log{K})$ 。
空间复杂度：只需要常数个变量来存储中间结果，所以空间复杂度为 $\mathcal{O}(1)$ 。