QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#133949#6264. Lucky DrawKhNURE_KIVI#AC ✓750ms1041924kbC++173.3kb2023-08-02 17:59:042023-08-02 17:59:07

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-08-02 17:59:07]
  • 评测
  • 测评结果:AC
  • 用时:750ms
  • 内存:1041924kb
  • [2023-08-02 17:59:04]
  • 提交

answer

//#pragma GCC optimize("Ofast", "unroll-loops")
//#pragma GCC target("sse", "sse2", "sse3", "ssse3", "sse4")
#ifdef LOCAL
#include <iostream>
#include <cmath>
#include <algorithm>
#include <stdio.h>
#include <cstdint>
#include <cstring>
#include <string>
#include <cstdlib>
#include <vector>
#include <bitset>
#include <map>
#include <queue>
#include <ctime>
#include <stack>
#include <set>
#include <list>
#include <random>
#include <deque>
#include <functional>
#include <iomanip>
#include <sstream>
#include <fstream>
#include <complex>
#include <numeric>
#include <cassert>
#include <array>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <thread>
#else
#include <bits/stdc++.h>
#endif

#define all(a) a.begin(),a.end()
#define len(a) (int)(a.size())
#define mp make_pair
#define pb push_back
#define fir first
#define sec second
#define fi first
#define se second

using namespace std;

typedef pair<int, int> pii;
typedef long long ll;
typedef __float128 ld;

template<typename T>
inline bool umin(T &a, T b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}

template<typename T>
inline bool umax(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

#ifdef LOCAL
#define D for (bool _FLAG = true; _FLAG; _FLAG = false)
#define LOG(...) print(#__VA_ARGS__" ::", __VA_ARGS__) << endl
template <class ...Ts> auto &print(Ts ...ts) { return ((cerr << ts << " "), ...); }
#else
#define D while (false)
#define LOG(...)
#endif // LOCAL

const int max_n = 8001, inf = 1000111222;

ld dp[max_n][max_n] = {}, C[max_n][max_n] = {};


int main() {
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int a, b, k,  n;
    long double p;
    cin >> n >> k >> p;
    vector <ld> d(n + 1), P(n + 1), PP(n + 1);
    PP[0] = P[0] = 1;
    C[0][0] = 1;
    for (int i = 1; i < max_n; i++) {
        C[i][0] = C[i][i] = 1;
        for (int j = 1; j < i; j++) {
            C[i][j] = C[i - 1][j] + C[i - 1][j - 1];
        }
    }
    for (int i = 1; i <= n; i++) {
        P[i] = P[i - 1] * p;
        PP[i] = PP[i - 1] * (1 - p);
    }
    d[0] = 1;
    d[1] = 0;
    cout << fixed;
    cout.precision(10);
    for (int i = 2; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            d[i] += d[i - j] * PP[j] * P[i - j];
        }
        d[i] /= 1 - P[i];
    }
    ld ans = 0;
    cout << fixed;
    cout.precision(10);
    dp[0][k] = 1;
    for (int i = 0; i + 1 < max_n; i++) {
        for (int j = 1; j <= k; j++) {
            dp[i + 1][j] += dp[i][j] * p;
            dp[i + 1][j - 1] += dp[i][j] * (1 - p);
        }
    }
    ld bad = 0;
    vector <ld> BB(n + 1);
    for (int day = 0; day < max_n; day++) {
        bad += dp[day][0];
        ld good = dp[day][1];
        ld GG = good;
        BB[0] = 1;
        for (int j = 1; j <= n; j++) {
            BB[j] = BB[j - 1] * bad;
        }
        for (int cnt = 2; cnt <= n; cnt++) {
            GG *= good;
            ans += C[n][cnt] * GG * BB[n - cnt] * PP[cnt];
        }
    }
    cout << (long double)ans << '\n';
    LOG(d[n]);
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 688ms
memory: 1034348kb

input:

2 2 0.5

output:

0.1851851852

result:

ok found '0.1851852', expected '0.1851852', error '0.0000000'

Test #2:

score: 0
Accepted
time: 658ms
memory: 1035308kb

input:

2 2 0.8

output:

0.0562414266

result:

ok found '0.0562414', expected '0.0562414', error '0.0000000'

Test #3:

score: 0
Accepted
time: 673ms
memory: 1036212kb

input:

5 3 0.85

output:

0.0454639641

result:

ok found '0.0454640', expected '0.0454640', error '0.0000000'

Test #4:

score: 0
Accepted
time: 667ms
memory: 1035436kb

input:

10 1 0.1

output:

0.5591865022

result:

ok found '0.5591865', expected '0.5591865', error '0.0000000'

Test #5:

score: 0
Accepted
time: 659ms
memory: 1034832kb

input:

10 1 0.5

output:

0.2787543425

result:

ok found '0.2787543', expected '0.2787543', error '0.0000000'

Test #6:

score: 0
Accepted
time: 674ms
memory: 1035612kb

input:

10 1 0.9

output:

0.0508778419

result:

ok found '0.0508778', expected '0.0508778', error '0.0000000'

Test #7:

score: 0
Accepted
time: 722ms
memory: 1036040kb

input:

10 2 0.1

output:

0.5327341098

result:

ok found '0.5327341', expected '0.5327341', error '0.0000000'

Test #8:

score: 0
Accepted
time: 673ms
memory: 1034688kb

input:

10 2 0.5

output:

0.2268908997

result:

ok found '0.2268909', expected '0.2268909', error '0.0000000'

Test #9:

score: 0
Accepted
time: 707ms
memory: 1034748kb

input:

10 2 0.9

output:

0.0391649075

result:

ok found '0.0391649', expected '0.0391649', error '0.0000000'

Test #10:

score: 0
Accepted
time: 694ms
memory: 1035232kb

input:

10 3 0.1

output:

0.5230588549

result:

ok found '0.5230589', expected '0.5230589', error '0.0000000'

Test #11:

score: 0
Accepted
time: 699ms
memory: 1034768kb

input:

10 3 0.5

output:

0.1993673560

result:

ok found '0.1993674', expected '0.1993674', error '0.0000000'

Test #12:

score: 0
Accepted
time: 674ms
memory: 1035820kb

input:

10 3 0.9

output:

0.0335953024

result:

ok found '0.0335953', expected '0.0335953', error '0.0000000'

Test #13:

score: 0
Accepted
time: 686ms
memory: 1040820kb

input:

10 50 0.1

output:

0.2312509917

result:

ok found '0.2312510', expected '0.2312510', error '0.0000000'

Test #14:

score: 0
Accepted
time: 750ms
memory: 1040700kb

input:

10 50 0.5

output:

0.0670958172

result:

ok found '0.0670958', expected '0.0670958', error '0.0000000'

Test #15:

score: 0
Accepted
time: 707ms
memory: 1040672kb

input:

10 50 0.9

output:

0.0103571503

result:

ok found '0.0103572', expected '0.0103572', error '0.0000000'

Test #16:

score: 0
Accepted
time: 680ms
memory: 1034908kb

input:

2 1 0.1

output:

0.8181818182

result:

ok found '0.8181818', expected '0.8181818', error '0.0000000'

Test #17:

score: 0
Accepted
time: 649ms
memory: 1034516kb

input:

2 1 0.5

output:

0.3333333333

result:

ok found '0.3333333', expected '0.3333333', error '0.0000000'

Test #18:

score: 0
Accepted
time: 658ms
memory: 1034940kb

input:

2 1 0.9

output:

0.0526315789

result:

ok found '0.0526316', expected '0.0526316', error '0.0000000'

Test #19:

score: 0
Accepted
time: 669ms
memory: 1034444kb

input:

2 2 0.1

output:

0.6829451540

result:

ok found '0.6829452', expected '0.6829452', error '0.0000000'

Test #20:

score: 0
Accepted
time: 654ms
memory: 1034952kb

input:

2 2 0.5

output:

0.1851851852

result:

ok found '0.1851852', expected '0.1851852', error '0.0000000'

Test #21:

score: 0
Accepted
time: 640ms
memory: 1034608kb

input:

2 2 0.9

output:

0.0263886864

result:

ok found '0.0263887', expected '0.0263887', error '0.0000000'

Test #22:

score: 0
Accepted
time: 643ms
memory: 1035416kb

input:

2 3 0.1

output:

0.5812382413

result:

ok found '0.5812382', expected '0.5812382', error '0.0000000'

Test #23:

score: 0
Accepted
time: 686ms
memory: 1035044kb

input:

2 3 0.5

output:

0.1358024691

result:

ok found '0.1358025', expected '0.1358025', error '0.0000000'

Test #24:

score: 0
Accepted
time: 678ms
memory: 1035412kb

input:

2 3 0.9

output:

0.0197734420

result:

ok found '0.0197734', expected '0.0197734', error '0.0000000'

Test #25:

score: 0
Accepted
time: 692ms
memory: 1041572kb

input:

2 50 0.1

output:

0.1156589757

result:

ok found '0.1156590', expected '0.1156590', error '0.0000000'

Test #26:

score: 0
Accepted
time: 667ms
memory: 1041272kb

input:

2 50 0.5

output:

0.0284416460

result:

ok found '0.0284416', expected '0.0284416', error '0.0000000'

Test #27:

score: 0
Accepted
time: 705ms
memory: 1040276kb

input:

2 50 0.9

output:

0.0042371527

result:

ok found '0.0042372', expected '0.0042372', error '0.0000000'

Test #28:

score: 0
Accepted
time: 645ms
memory: 1035908kb

input:

3 1 0.1

output:

0.7518427518

result:

ok found '0.7518428', expected '0.7518428', error '0.0000000'

Test #29:

score: 0
Accepted
time: 665ms
memory: 1034168kb

input:

3 1 0.5

output:

0.2857142857

result:

ok found '0.2857143', expected '0.2857143', error '0.0000000'

Test #30:

score: 0
Accepted
time: 661ms
memory: 1035272kb

input:

3 1 0.9

output:

0.0508836667

result:

ok found '0.0508837', expected '0.0508837', error '0.0000000'

Test #31:

score: 0
Accepted
time: 629ms
memory: 1035676kb

input:

3 2 0.1

output:

0.6012335751

result:

ok found '0.6012336', expected '0.6012336', error '0.0000000'

Test #32:

score: 0
Accepted
time: 675ms
memory: 1034676kb

input:

3 2 0.5

output:

0.1961219862

result:

ok found '0.1961220', expected '0.1961220', error '0.0000000'

Test #33:

score: 0
Accepted
time: 660ms
memory: 1034716kb

input:

3 2 0.9

output:

0.0317973920

result:

ok found '0.0317974', expected '0.0317974', error '0.0000000'

Test #34:

score: 0
Accepted
time: 629ms
memory: 1035548kb

input:

3 3 0.1

output:

0.5081695513

result:

ok found '0.5081696', expected '0.5081696', error '0.0000000'

Test #35:

score: 0
Accepted
time: 674ms
memory: 1034688kb

input:

3 3 0.5

output:

0.1599825613

result:

ok found '0.1599826', expected '0.1599826', error '0.0000000'

Test #36:

score: 0
Accepted
time: 659ms
memory: 1034836kb

input:

3 3 0.9

output:

0.0252285784

result:

ok found '0.0252286', expected '0.0252286', error '0.0000000'

Test #37:

score: 0
Accepted
time: 704ms
memory: 1041140kb

input:

3 50 0.1

output:

0.1561194082

result:

ok found '0.1561194', expected '0.1561194', error '0.0000000'

Test #38:

score: 0
Accepted
time: 681ms
memory: 1041340kb

input:

3 50 0.5

output:

0.0407935056

result:

ok found '0.0407935', expected '0.0407935', error '0.0000000'

Test #39:

score: 0
Accepted
time: 718ms
memory: 1041764kb

input:

3 50 0.9

output:

0.0061485940

result:

ok found '0.0061486', expected '0.0061486', error '0.0000000'

Test #40:

score: 0
Accepted
time: 710ms
memory: 1034472kb

input:

50 1 0.1

output:

0.6514034856

result:

ok found '0.6514035', expected '0.6514035', error '0.0000000'

Test #41:

score: 0
Accepted
time: 701ms
memory: 1034616kb

input:

50 1 0.5

output:

0.2786470731

result:

ok found '0.2786471', expected '0.2786471', error '0.0000000'

Test #42:

score: 0
Accepted
time: 678ms
memory: 1034332kb

input:

50 1 0.9

output:

0.0508778419

result:

ok found '0.0508778', expected '0.0508778', error '0.0000000'

Test #43:

score: 0
Accepted
time: 718ms
memory: 1034472kb

input:

50 2 0.1

output:

0.5399494385

result:

ok found '0.5399494', expected '0.5399494', error '0.0000000'

Test #44:

score: 0
Accepted
time: 715ms
memory: 1035048kb

input:

50 2 0.5

output:

0.2433956615

result:

ok found '0.2433957', expected '0.2433957', error '0.0000000'

Test #45:

score: 0
Accepted
time: 722ms
memory: 1035432kb

input:

50 2 0.9

output:

0.0429634758

result:

ok found '0.0429635', expected '0.0429635', error '0.0000000'

Test #46:

score: 0
Accepted
time: 723ms
memory: 1036084kb

input:

50 3 0.1

output:

0.5433728095

result:

ok found '0.5433728', expected '0.5433728', error '0.0000000'

Test #47:

score: 0
Accepted
time: 693ms
memory: 1035968kb

input:

50 3 0.5

output:

0.2220571015

result:

ok found '0.2220571', expected '0.2220571', error '0.0000000'

Test #48:

score: 0
Accepted
time: 701ms
memory: 1034700kb

input:

50 3 0.9

output:

0.0384784231

result:

ok found '0.0384784', expected '0.0384784', error '0.0000000'

Test #49:

score: 0
Accepted
time: 722ms
memory: 1041924kb

input:

50 50 0.1

output:

0.2868244322

result:

ok found '0.2868244', expected '0.2868244', error '0.0000000'

Test #50:

score: 0
Accepted
time: 693ms
memory: 1040868kb

input:

50 50 0.5

output:

0.0895002371

result:

ok found '0.0895002', expected '0.0895002', error '0.0000000'

Test #51:

score: 0
Accepted
time: 740ms
memory: 1041308kb

input:

50 50 0.9

output:

0.0140856521

result:

ok found '0.0140857', expected '0.0140857', error '0.0000000'