1. 题目

输入描述:

$0 \leq r _ i, p _ i \leq 100$

样例输入

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


样例输出

880839106


题解

emmm 就是期望背包嘛

。。。

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

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

$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;
}