1. 题目

题目描述

小 N 是一家金融公司的项目经理。他准备投资一个项目，这个项目要融资 $L$元，融资成功后会得到 $M$元的利润。现在有 $n$个客户。对于第 $i$个客户，他有 $m _ i$元钱。小 N 承诺假如最后筹够钱，会给这名客户 $m _ i \times r _ i$的分红。小 L 通过迷之手段，估计出这个客户最后愿意出钱的概率为 $p _ i$。 注意，假如公司最后筹够钱，但最终给客户分红比赚的多，他还是需要分出这么多的钱（相当于亏钱了）。现在小 L 想知道，按前面这样说的去做，公司最后期望能赚多少钱（有可能是负数）。

输入描述:

第一行三个个整数 $n, L, M$。
接下来 n 行，每行三个整数 $m _ i, R _ i, P _ i$. 其中 $r _ i = \frac {R _ i} {100}, p _ i = \frac {P _ i} {100}$.
数据保证 $0 \leq n \leq 100$, $\sum _ {i = 1} ^ n m _ i \leq 500000$, $0 \leq L,M \leq 100000$。
$0 \leq r _ i, p _ i \leq 100$

输出描述:

一行一个整数代表公司最后期望收益对 $10 ^ 9 + 7$取模的值。一个分数对 $10 ^ 9 + 7$取模的值，相当于 A 乘上 B 的逆元再对 $10 ^ 9 + 7$取模。

样例输入

4 89 88
99 16 80
76 1 6
81 16 70
37 3 96

样例输出

880839106

题解

最近这个牛客网推广做的非常棒啊

到处都有这个牛客网。。。

emmm 就是期望背包嘛

。。。

可是 XZY 太弱了连期望背包都没做过.jpg

首先可以想到设状态：

$g[i][j]$表示前 $i$个人，筹集到 $j$块钱的期望支出。

然后就会发现 $g[i][j]$并不能单纯地从 $g[i – 1][j]$和 $g[i – 1][j – m[i]]$转移过来——因为 $g[i – 1][j], g[i – 1][j – m[i]]$这两个状态不一定存在。

原因是第 $i$个人并不是独立于前 $i – 1$个人的，因此概率与期望并不能这样单纯地计算。

可以想到再设一个 $f[i][j]$表示前 $i$个人筹集到 $j$块钱的概率。

那么这个就很简单了，就是个 01 背包：

$f[i][j] = p[i] \times f[i – 1][j – m[i]] + (1 – p[i]) \times f[i – 1][j]$

然后就能计算 $g$了：

$g[i][j] = (1 – p[i]) \times g[i – 1][j] + p[i] \times (g[i – 1][j – m[i]] + f[i – 1][j – m[i]] \times m[i] \times r[i])$

恩，然后滚动一下数组就行了。

代码：

#include <bits/stdc++.h>

#define NS (105)
#define MS (50000005)
#define MOD (1000000007)
#define IV100 (570000004)

using namespace std;

template <typename _Tp> inline void IN(_Tp& dig)
{
    char c; bool flag = 0; dig = 0;
    while (c = getchar(), !isdigit(c)) if (c == '-') flag = 1;
    while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
    if (flag) dig = -dig;
}

int pls(int a, int b) {return a + b >= MOD ? a + b - MOD : a + b;}
int mns(int a, int b) {return a - b < 0 ? a - b + MOD : a - b;}
int mul(int a, int b) {return 1ll * a * b % MOD;}

int n, L, M, x[NS], r[NS], p[NS], f[MS], g[MS];

int main(int argc, char const* argv[])
{
    IN(n), IN(L), IN(M); int tot = 0;
    for (int i = 1; i <= n; i += 1)
    {
        IN(x[i]), IN(r[i]), IN(p[i]), tot += x[i];
        r[i] = mul(r[i], IV100), p[i] = mul(p[i], IV100);
    }
    f[0] = 1;
    for (int i = 1; i <= n; i += 1)
        for (int j = tot; j >= 0; j -= 1)
        {
            g[j] = mul(g[j], mns(1, p[i]));
            if (j >= x[i])
                g[j] = pls(g[j],
                    mul(pls(g[j - x[i]], mul(mul(x[i], r[i]), f[j - x[i]])), p[i]));
            f[j] = mul(f[j], mns(1, p[i]));
            if (j >= x[i]) f[j] = pls(f[j], mul(f[j - x[i]], p[i]));
        }
    int ans = 0;
    for (int i = L; i <= tot; i += 1) ans = pls(ans, mns(mul(M, f[i]), g[i]));
    printf("%d\n", ans);
    return 0;
}