「Wannafly 023C」收益

题目大意：小N准备投资一个要融资 $L$ 元的项目，融资成功后会得到 $M$ 元的利润。现在有 $n$ 个客户，第 $i$ 个客户有 $m_i$ 元钱，且最后愿意出钱的概率为 $p_i$，小N承诺假如最后筹够钱，会给这名客户 $m_i \times r_i$ 的分红。请你求出最后期望能赚多少钱（有可能是负数）。$0 \leq n \leq 100, 0 \leq L,M \leq 100000$

在概率论和统计学中，数学期望(mean)（或均值，亦简称期望）是试验中每次可能结果的概率乘以其结果的总和，是最基本的数学特征之一。它反映随机变量平均取值的大小。

设 $f[i][j]$ 表示前 $i$ 个客户筹到 $j$ 元钱的概率，$g[i][j]$ 表示前 $i$ 个客户筹到 $j$ 元钱的期望分红，概率背包。

#include <cstdio>
 
const int N = 105, X = 500005, P = 1e9+7, Inv = 570000004;
int n, sum, L, M, F, G, m[N], r[N], p[N], f[X], g[X];
 
int min(int x, int y) {
    return x < y ? x : y;
}
 
int main() {
    scanf("%d%d%d", &n, &L, &M);
    for (int i = 1; i <= n; ++i) {
        scanf("%d%d%d", &m[i], &r[i], &p[i]);
        r[i] = 1LL * r[i] * m[i] % P * Inv % P;
        p[i] = 1LL * p[i] * Inv % P, sum += m[i];
    }
    f[0] = 1;
    for (int i = 1; i <= n; ++i) {
        for (int j = sum; j >= m[i]; --j) {
            f[j] = (1LL * f[j] * (1 - p[i] + P) + 1LL * f[j-m[i]] * p[i]) % P;
            g[j] = (1LL * g[j] * (1 - p[i] + P) + (1LL * r[i] * f[j-m[i]] % P + g[j-m[i]]) * p[i]) % P;
        }
        for (int j = m[i] - 1; j >= 0; --j) {
            f[j] = 1LL * f[j] * (1 - p[i] + P) % P;
            g[j] = 1LL * g[j] * (1 - p[i] + P) % P;
        }
    }
    for (int i = L; i <= sum; ++i)
        F = (F + f[i]) % P, G = (G + g[i]) % P;
    printf("%lld\n", (1LL * F * M - G + P) % P);
    return 0;
}

时间复杂度 $O(n\sum\limits_{i=1}^{n} m_i)$