NC18389 收益
题目链接
题目
题目描述
小N是一家金融公司的项目经理。他准备投资一个项目，这个项目要融资L元，融资成功后会得到M元的利润。现在有n个客户。对于第i个客户，他有mi元钱。小N承诺假如最后筹够钱，会给这名客户mi x ri的分红。小L通过迷之手段，估计出这个客户最后愿意出钱的概率为pi。 注意，假如公司最后筹够钱，但最终给客户分红比赚的多，他还是需要分出这么多的钱（相当于亏钱了）。现在小L想知道，按前面这样说的去做，公司最后期望能赚多少钱（有可能是负数）。
输入描述
第一行三个个整数n, L, M。
接下来n行，每行三个整数mi, Ri, Pi. 其中 \(r_i = \frac{R_i}{100}, p_i = \frac{P_i}{100}\) .
数据保证 0 ≤ n ≤ 100, \(\sum_{i=1}^n m_i \leq 500000\) , 0 ≤ L,M ≤ 100000。
0 ≤ ri, pi ≤ 100
输出描述
一行一个整数代表公司最后期望收益对10^9 + 7取模的值。一个分数 \(\frac{A}{B}\) 对109+7取模的值，相当于A乘上B的逆元再对109+7取模。
示例1
输入
4 89 88
99 16 80
76 1 6
81 16 70
37 3 96
输出
880839106
题解
知识点：概率dp，背包dp。
考虑设 \(f_{i,j}\) 为考虑了前 \(i\) 个客户获得了 \(j\) 元的期望分红。
由于获得 \(j\) 元的概率都不一致，因此每次加上去的期望都要乘一个概率，所以我们需要记录每种可能的概率。
设 \(g_{i,j}\) 表示考虑了前 \(i\) 个客户获得了 \(j\) 元的概率，那么转移方程显然：
\[\begin{aligned}
f_{i,j} &= f_{i-1,j} \cdot (1-p_{i})\\
f_{i,\min\{ j + m_i \cdot r_i,L \}} &= f_{i-1,j} \cdot p_{i}\\
g_{i,j} &= g_{i-1,j} \cdot (1-p_{i})\\
g_{i,\min\{ j + m_i \cdot r_i,L \}} &= (g_{i-1,j} + f_{i-1,j} \cdot m_i \cdot r_i) \cdot p_{i}
\end{aligned}
\]
最后答案为 \(f_{n,L} \cdot M - g_{n,L}\) 。
时间复杂度 \(O(nL)\)
空间复杂度 \(O(L)\)
代码
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int P = 1e9 + 7;
const int base = 570000004;
int m[107], p[107], r[107];
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n, L, M;
cin >> n >> L >> M;
for (int i = 1;i <= n;i++) {
cin >> m[i] >> r[i] >> p[i];
r[i] = 1LL * r[i] * m[i] % P * base % P;
p[i] = 1LL * p[i] * base % P;
}
vector<int> f(L + 1), g(L + 1);
f[0] = 1;
for (int i = 1;i <= n;i++) {
vector<int> ff(L + 1), gg(L + 1);
for (int j = 0;j <= L;j++) {
(ff[j] += 1LL * f[j] * (1 - p[i] + P) % P) %= P;
(ff[min(j + m[i], L)] += 1LL * f[j] * p[i] % P) %= P;
(gg[j] += 1LL * g[j] * (1 - p[i] + P) % P) %= P;
(gg[min(j + m[i], L)] += 1LL * (g[j] + 1LL * r[i] * f[j] % P) * p[i] % P) %= P;
}
f = ff;
g = gg;
}
cout << (1LL * f[L] * M % P - g[L] + P) % P << '\n';
return 0;
}