CF1925D Good Trip

一道概率期望题，赛时以为是不会做的概率 dp，赛后发现其实是个很简单的概率期望数学题，只要找到结论推出式子即可，非常简单。

题目大意

一个班有 $n$ 个孩子，其中 $m$ 对是朋友。其中 $i$ 对是朋友，他们的友谊值为 $f_i$ 。

老师要去 $k$ 次远足，每次远足她都会随机、等价、独立地选择一对孩子。如果选择了一对是朋友的孩子，他们的友谊值在 以后的所有远足 中都会增加 $1$ (教师可以多次选择一对孩子)。如果一对儿童不是朋友，那么他们的友谊值为 $0$ ，在以后的游览中不会改变。

求所有 被选中参加远足 的 $k$ 对的友谊值总和的期望值(在被选中时)。可以证明，这个答案总是可以用分数 $\dfrac{p}{q}$ 表示，其中 $p$ 和 $q$ 是整数。计算 $p\cdot q^{-1} \bmod (10^9+7)$ 。

思路

不难发现，总的友谊值和是由两个独立的部分组成的：选中一对朋友产生的友谊值本身，和多次选中同一对朋友产生的附加友谊值。

记 $S = \dfrac{n(n-1)}{2}$ 为单次出行的方案总数。

单独考虑这两个部分的期望。

对于第一部分，显然，对于一对朋友，它产生的期望值为 $f_i \times \dfrac{k}{S}$，所有朋友产生的总期望值为 $\sum{f_i} \times \dfrac{k}{S}$。

对于第二部分，我们不难发现，如果一对朋友在 $k$ 次远足中总共被选择了 $x$ 次，那么它将会产生 $0 + 1 + … + (x-1) = \dfrac{x(x-1)}{2}$ 的贡献，而这对朋友在 $k$ 次远足中被选择 $x$ 次的概率为 ${n \choose m} ({\dfrac{1}{S}})^x (\dfrac{S-1}{S})^{k - x}$。因此，每对朋友产生的期望值为 ${n \choose m} ({\dfrac{1}{S}})^x (\dfrac{S-1}{S})^{k - x} \dfrac{x(x-1)}{2}$，共有 $m$ 对朋友，将这个期望值乘上 $m$，即为总的期望值。

两个部分的期望相加，得到最后的期望。

代码

#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7, maxn = 2e5 + 5;
long long ksm(long long a, long long b) {
    long long base = a % mod, res = 1;
    while (b) {
        if (b & 1) {
            (res *= base) %= mod;
        }
        (base *= base) %= mod;
        b >>= 1;
    }
    return res;
}
int n, m, k;
long long fact[maxn];
void init() {
    fact[0] = fact[1] = 1;
    for (int i = 2; i <= 2e5; i++) {
        fact[i] = (fact[i - 1] * i) % mod;
    }
}
long long rev(long long x) {
    return ksm(x, mod - 2);
}
long long c(int n, int m) {
    return fact[n] * rev(fact[n - m]) % mod * rev(fact[m]) % mod;
}
int main() {
    cin.tie(0)->sync_with_stdio(0);
    init();
    int t;
    cin >> t;
    while (t--) {
        long long sum = 0, res = 0;
        cin >> n >> m >> k;
        long long s = 1ll * (n - 1) * n / 2, revs = ksm(s, mod - 2);
        for (int i = 0, f; i < m; i++) {
            cin >> f >> f >> f;
            (sum += f) %= mod;
        }
        res += sum * k % mod * revs % mod;
        for (int i = 2; i <= k; i++) {
            (res += m * c(k, i) % mod * ksm(rev(s), i) % mod * ksm((s - 1) % mod * rev(s) % mod, k - i) % mod * (1ll * i * (i - 1) / 2 % mod) % mod) %= mod;
        }
        cout << res << "\n";
    }
    return 0;
}