QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#714655 | #6264. Lucky Draw | holao09 | AC ✓ | 721ms | 1043620kb | C++14 | 3.3kb | 2024-11-06 01:53:13 | 2024-11-06 01:53:13 |
Judging History
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'