Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <assert.h>
- #include <bits/stdc++.h>
- using namespace std;
- #ifndef __DEBUG__
- #define dbg(...) 42
- #endif
- template <class T>
- using mpq = priority_queue<T, vector<T>, greater<T>>;
- using ll = long long;
- using pii = pair<int, int>;
- using pll = pair<ll, ll>;
- using vl = vector<ll>;
- using vi = vector<int>;
- int main(int argc, char **argv) {
- ll n, x;
- cin >> n >> x;
- vl ps(n);
- for (auto &x : ps)
- cin >> x;
- vector<vector<double>> prob(n, vector<double>(n + 1)); // 一次抽卡, 考虑前i项获得j张卡的概率
- prob[0][0] = 1 - (ps[0] / 100.0);
- prob[0][1] = ps[0] / 100.0;
- for (ll i = 1; i < n; ++i) {
- double p = ps[i] / 100.0;
- prob[i] = prob[i - 1];
- for (auto &v : prob[i])
- v *= (1 - p);
- for (ll j = 1; j <= i + 1; ++j) {
- double pprev = prob[i - 1][j - 1];
- prob[i][j] += pprev * p;
- }
- }
- const auto &pt = prob.back();
- dbg(pt);
- assert(abs(accumulate(pt.begin(), pt.end(), 0.0, std::plus<>()) - 1) < 1e-6);
- vector<double> expect(x + 1);
- auto search = [&](auto &&self, ll v) -> double {
- if (v < 0)
- return 1.0;
- if (expect[v] != 0)
- return expect[v];
- double factor = 1 - pt[0], eacc = 0;
- for (ll i = 1; i <= min(n, v); ++i) {
- eacc += pt[i] * self(self, v - i);
- }
- double full = 0;
- for (ll i = min(n, v); i <= n; ++i) {
- full += pt[i];
- }
- return expect[v] = eacc / factor;
- };
- search(search, x);
- dbg(expect);
- cout << expect[x] << '\n';
- return 0;
- };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement