Advertisement
pb_jiang

ABC382E

Nov 30th, 2024
65
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.65 KB | None | 0 0
  1. #include <assert.h>
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4. #ifndef __DEBUG__
  5. #define dbg(...) 42
  6. #endif
  7. template <class T>
  8. using mpq = priority_queue<T, vector<T>, greater<T>>;
  9.  
  10. using ll = long long;
  11. using pii = pair<int, int>;
  12. using pll = pair<ll, ll>;
  13. using vl = vector<ll>;
  14. using vi = vector<int>;
  15.  
  16. int main(int argc, char **argv) {
  17.     ll n, x;
  18.     cin >> n >> x;
  19.     vl ps(n);
  20.     for (auto &x : ps)
  21.         cin >> x;
  22.  
  23.     vector<vector<double>> prob(n, vector<double>(n + 1));  // 一次抽卡, 考虑前i项获得j张卡的概率
  24.  
  25.     prob[0][0] = 1 - (ps[0] / 100.0);
  26.     prob[0][1] = ps[0] / 100.0;
  27.     for (ll i = 1; i < n; ++i) {
  28.         double p = ps[i] / 100.0;
  29.         prob[i] = prob[i - 1];
  30.         for (auto &v : prob[i])
  31.             v *= (1 - p);
  32.  
  33.         for (ll j = 1; j <= i + 1; ++j) {
  34.             double pprev = prob[i - 1][j - 1];
  35.             prob[i][j] += pprev * p;
  36.         }
  37.     }
  38.  
  39.     const auto &pt = prob.back();
  40.     dbg(pt);
  41.     assert(abs(accumulate(pt.begin(), pt.end(), 0.0, std::plus<>()) - 1) < 1e-6);
  42.  
  43.     vector<double> expect(x + 1);
  44.     auto search = [&](auto &&self, ll v) -> double {
  45.         if (v < 0)
  46.             return 1.0;
  47.         if (expect[v] != 0)
  48.             return expect[v];
  49.         double factor = 1 - pt[0], eacc = 0;
  50.         for (ll i = 1; i <= min(n, v); ++i) {
  51.             eacc += pt[i] * self(self, v - i);
  52.         }
  53.         double full = 0;
  54.         for (ll i = min(n, v); i <= n; ++i) {
  55.             full += pt[i];
  56.         }
  57.         return expect[v] = eacc / factor;
  58.     };
  59.  
  60.     search(search, x);
  61.     dbg(expect);
  62.     cout << expect[x] << '\n';
  63.     return 0;
  64. };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement