QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#714655#6264. Lucky Drawholao09AC ✓721ms1043620kbC++143.3kb2024-11-06 01:53:132024-11-06 01:53:13

Judging History

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

  • [2024-11-06 01:53:13]
  • 评测
  • 测评结果:AC
  • 用时:721ms
  • 内存:1043620kb
  • [2024-11-06 01:53:13]
  • 提交

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: 608ms
memory: 1037408kb

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: 565ms
memory: 1035652kb

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: 628ms
memory: 1035616kb

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: 609ms
memory: 1035484kb

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: 681ms
memory: 1035364kb

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: 648ms
memory: 1037576kb

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: 637ms
memory: 1035708kb

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: 636ms
memory: 1035480kb

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: 644ms
memory: 1035428kb

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: 629ms
memory: 1035616kb

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: 632ms
memory: 1035620kb

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: 617ms
memory: 1037584kb

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: 677ms
memory: 1041480kb

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: 654ms
memory: 1043516kb

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: 639ms
memory: 1043620kb

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: 649ms
memory: 1037288kb

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: 655ms
memory: 1037412kb

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: 668ms
memory: 1035424kb

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: 606ms
memory: 1035496kb

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: 666ms
memory: 1035584kb

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: 647ms
memory: 1037468kb

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: 624ms
memory: 1035612kb

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: 622ms
memory: 1035840kb

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: 631ms
memory: 1035672kb

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: 664ms
memory: 1041588kb

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: 590ms
memory: 1043592kb

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: 660ms
memory: 1041592kb

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: 630ms
memory: 1035424kb

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: 681ms
memory: 1037588kb

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: 623ms
memory: 1035392kb

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: 637ms
memory: 1035588kb

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: 652ms
memory: 1035584kb

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: 627ms
memory: 1035620kb

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: 608ms
memory: 1035616kb

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: 630ms
memory: 1037712kb

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: 660ms
memory: 1035712kb

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: 680ms
memory: 1041548kb

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: 683ms
memory: 1041720kb

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: 644ms
memory: 1043404kb

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: 653ms
memory: 1037344kb

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: 660ms
memory: 1035356kb

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: 669ms
memory: 1035372kb

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: 643ms
memory: 1035432kb

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: 638ms
memory: 1037468kb

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: 667ms
memory: 1035484kb

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: 686ms
memory: 1037596kb

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: 718ms
memory: 1035676kb

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: 680ms
memory: 1035744kb

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: 679ms
memory: 1041592kb

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: 721ms
memory: 1041608kb

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: 719ms
memory: 1043456kb

input:

50 50 0.9

output:

0.0140856521

result:

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