抢红包题解

出题

---

当 $n=1$ 时，期望值为 $m$。

当 $n=2$ 时，若 $m$ 为偶数直接输出 $\frac{m}{2}$，为奇数则输出 $\frac{m+p}{2}$，可通过 $10\%$ 的数据。

---

出题人本意是想出一道概率 dp，没想到现场有人写出了更快更好的解法，因此题目难度与出题人预料的不符，根本达不到 hard，这里直接放上现场 AC 的更快的解法，先膜一下 %%%。

更快的解法

由于每个人获得红包的分数等概率地分布在 $[1,x-(n-i)]$ 区间，因此第 $i$ 个人获得红包的期望就是 $\frac{1+(x-(n-i))}{2}$，其中 $x$ 为到第 $i$ 个人时剩余的红包分数期望，最后按题意从 $1$ 到 $n$ 模拟推期望即可。出题人的龟速解法不看也罢，可直接跳转至更快的标程，点击此处跳转 AC 提交。

出题人的龟速解法

设 dp[i][j] 表示前 $i$ 个人总共领到 $j$ 分红包的概率，则有：

$$dp[0][0]=1\tag{1}$$

$$dp[i][j]=\sum_{k=i-1}^{j-1}dp[i-1][k]\times\frac{1}{m-(n-i)-k}\quad j\in[i,m-(n-i)]\tag{2}$$

$$ans=\sum_{j=n-1}^{m-1}dp[n-1][j]\times(m-j)\tag{3}$$

公式 (2) 表示前 $i$ 个人共分到 $j$ 分红包的概率等于前 $i-1$ 个人共分到 $k$ 分红包的概率乘上第 $i$ 个人能分到 $j-k$ 分红包的概率，此时第 $i$ 个人能分到的红包区间为 $[1,m-(n-i)-k]$，区间内每个值都是等概率被取到，即取到 $j-k$ 分的概率是 $\frac{1}{m-(n-i)-k}$。

公式 (3) 表示当前 $n-1$ 个人总共分到 $j$ 分红包时，最后一个人能被分到红包的分数为 $m-j$，再乘上对应的概率 dp[n-1][j] ，求和后就是最后一个人能被分到红包分数的期望。

这种解法的时间复杂度为 $O(nm^2)$，可通过 $60\%$ 的数据。

---

从公式 (2) 还可以发现求和的每一项在 $[i-1,j-1]$ 内是连续的区间，因此可以预处理前缀和将时间复杂度从 $O(nm^2)$ 降到 $O(nm)$，理论上算法时间复杂度已经可通过 $100\%$ 的数据，但还有一些细节需要优化。

---

最后的模数 $p=10^9+7$ 是一个质数，且所有除数均不为模数的倍数，可用 $O(n\log_2 p)$ 复杂度的费马小定理、扩展欧几里得或者 $O(n)$ 复杂度的线性预处理 $5000$ 以内的逆元，不预处理将在最终的时间复杂度上乘上一个 $\log_2 (10^9+7)$，导致超时。

观察递推式发现 dp[i] 的各项值只依赖 dp[i-1]，对 dp[j] $(j<i-1)$ 没有依赖，可以使用 $2m$ 大小的滚动数组递推，空间复杂度可为 $O(2m)$，$5000^2$ 的 long long 数组占 $\frac{5000^2\times8}{1024^2}\approx190MB$，题目限制 $128MB$ 内存，不进行优化将得到内存超限的结果。

两步优化后可通过 $100\%$ 的数据。

更快的标程

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL MOD = 1000000007;
int n;
LL m;
inline LL div2(LL x) {
    if (x >= MOD) {
        x -= MOD;
    }
    if (x % 2 == 0) {
        return x / 2;
    }
    return (x + MOD) / 2;
}
int main() {
    scanf("%d%lld", &n, &m);
    for (int i = 1; i < n; ++i) {
        LL l = 1;
        LL r = m - (n - i);
        m = ((m - div2(l + r)) % MOD + MOD) % MOD;
    }
    printf("%lld\n", m);
    return 0;
}

出题人的龟速标程

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 5000 + 100;
const LL MOD = 1000000007;
int n, m;
LL ans;
LL inv[maxn];
LL dp[2][maxn], sum[2][maxn];
void initInv() {
    inv[1] = 1;
    for(int i = 2; i < maxn; ++i) {
        inv[i] = (LL)(MOD - MOD / i) * inv[MOD % i] % MOD;
    }
}
int main() {
    initInv();
    scanf("%d%d", &n, &m);
    dp[0][0] = 1;
    for (int i = 1; i <= n; ++i) {
        int nowIndex = i & 1;
        int preIndex = nowIndex ^ 1;
        sum[preIndex][0] = dp[preIndex][0] * inv[m - (n - i)] % MOD;
        for (int j = 1; j < m - (n - i); ++j) {
            sum[preIndex][j] = (sum[preIndex][j - 1] + dp[preIndex][j] * inv[m - (n - i) - j] % MOD) % MOD;
        }
        for (int j = i; j <= m - (n - i); ++j) {
            if (i - 1 == 0) {
                dp[nowIndex][j] = sum[preIndex][j - 1];
            } else {
                dp[nowIndex][j] = ((sum[preIndex][j - 1] - sum[preIndex][i - 2]) % MOD + MOD) % MOD;
            }
        }
    }
    for (int j = n - 1; j <= m - 1; ++j) {
        int preIndex = (n - 1) & 1;
        ans = (ans + dp[preIndex][j] * (m - j) % MOD) % MOD;
    }
    printf("%lld\n", ans);
    return 0;
}

数据生成

#include <bits/stdc++.h>
using namespace std;
const int testCases = 50;
ofstream fout;
int getRand(int l, int r) {
    return rand() % (r - l + 1) + l;
}
string numToStr(int x) {
    string str;
    while (x != 0) {
        str = char('0' + x % 10) + str;
        x /= 10;
    }
    return str;
}
string getFileName(int index) {
    return "data/" + numToStr(index) + ".in";
}
int main() {
    srand(time(0));
    // data in 10%, 1 <= n <= 2, 1 <= m <= 100
    int one = testCases * 10 / 100;
    for (int i = 1; i <= one; ++i) {
        fout.open(getFileName(i));
        switch (getRand(1, 3)) {
        case 1:
            fout << "1 " << getRand(70, 100) << endl;
            break;
        case 2:
            fout << "2 " << getRand(40, 50) * 2 << endl;
            break;
        case 3:
            fout << "2 " << getRand(40, 50) * 2 - 1 << endl;
            break;
        }
        fout.close();
    }
    // data in 20%, 1 <= n <= m <= 100
    int two = testCases * 20 / 100;
    for (int i = one + 1; i <= two; ++i) {
        fout.open(getFileName(i));
        int n = getRand(10, 70);
        int m = getRand(n, 100);
        fout << n << " " << m << endl;
        fout.close();
    }
    // data in 100%, 1 <= n <= m <= 5000
    int three = testCases;
    for (int i = two + 1; i <= three; ++i) {
        fout.open(getFileName(i));
        int n = getRand(4000, 4700);
        int m = getRand(n, 5000);
        fout << n << " " << m << endl;
        fout.close();
    }
    return 0;
}