QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#108055#4228. Double SortzaxwellmenAC ✓611ms210824kbC++201.2kb2023-05-23 15:13:042023-05-23 15:13: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-05-23 15:13:07]
  • 评测
  • 测评结果:AC
  • 用时:611ms
  • 内存:210824kb
  • [2023-05-23 15:13:04]
  • 提交

answer

#include<bits/stdc++.h>

using namespace std;
typedef double db;
typedef pair<int, int> pi;

#define FOR(i, a, b) for (int i = (a); i < (b); i++) 
#define F0R(i, a) FOR(i, 0, a)
#define rsz resize
#define mp make_pair

int n, m;
db dp[51][10001][51];
db fact[10001], ch[10001][51];

// db choose(int n, int k) {
    // if (pre.find(mp(n,k)) != pre.end()) return pre[mp(n,k)];
    // if (k > n) return 0;
    // db ans = 1;
    // F0R(i, k) ans *= db(n-i) / db(i+1);
    // pre[mp(n,k)] = ans;
    // return ans;
// }

int main() {
    cin.tie(0) -> sync_with_stdio(0);
    F0R(k, 51) FOR(n, k, 10001) {
        ch[n][k] = 1;
        F0R(i, k) ch[n][k] *= db(n-i) / db(i+1);
    }
    fill(*dp[0], *dp[51], (db)1);
    cin >> n >> m;
    FOR(i, 1, n+1) {
        FOR(j, i, m+1) {
            db den = db(1) / ch[j][i];
            FOR(k, max(0, 2*i-j), i+1) {
                db prob = ch[i][k] * ch[j-i][i-k] * den;
                FOR(a, k, i) dp[i][j][a] += dp[i-k][j-i][a-k] * prob;
            }
        }
    }
    cout << fixed << setprecision(8);
    FOR(i, 1, n) dp[n][m][i] += dp[n][m][i-1];
    // cout << "done" << endl; return 0;
    F0R(i, n) cout << dp[n][m][i] << '\n';
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 44ms
memory: 210820kb

input:

3 5

output:

1.00000000
2.30000000
4.50000000

result:

ok 3 numbers

Test #2:

score: 0
Accepted
time: 48ms
memory: 210764kb

input:

5 17

output:

1.13138332
2.74838397
5.18309632
8.85568843
15.00000000

result:

ok 5 numbers

Test #3:

score: 0
Accepted
time: 611ms
memory: 210760kb

input:

50 10000

output:

4.43281643
12.83659687
25.31526873
41.95561124
62.84807606
88.08715468
117.77163378
152.00489478
190.89524200
234.55626293
283.10722438
336.67350947
395.38710039
459.38711351
528.82039390
603.84217776
684.61683284
771.31868857
864.13296997
963.25685207
1068.90065489
1181.28920327
1300.66338100
1427....

result:

ok 50 numbers

Test #4:

score: 0
Accepted
time: 20ms
memory: 210824kb

input:

40 40

output:

1.00000000
2.00000000
3.00000000
4.00000000
5.00000000
6.00000000
7.00000000
8.00000000
9.00000000
10.00000000
11.00000000
12.00000000
13.00000000
14.00000000
15.00000000
16.00000000
17.00000000
18.00000000
19.00000000
20.00000000
21.00000000
22.00000000
23.00000000
24.00000000
25.00000000
26.000000...

result:

ok 40 numbers

Test #5:

score: 0
Accepted
time: 32ms
memory: 210764kb

input:

39 1489

output:

1.52708756
3.93901257
7.34033024
11.76349375
17.23670136
23.79071092
31.45828771
40.27423309
50.27559105
61.50187530
73.99532470
87.80119513
102.96809478
119.54837093
137.59855864
157.17990423
178.35897978
201.20840937
225.80773368
252.24444743
280.61525535
311.02760710
343.60159349
378.47231670
415...

result:

ok 39 numbers

Test #6:

score: 0
Accepted
time: 497ms
memory: 210760kb

input:

47 9871

output:

4.88391759
14.20932202
28.09393481
46.64143097
69.96023578
98.16395174
131.37172305
169.70865107
213.30625266
262.30296659
316.84471482
377.08552607
443.18823073
515.32523741
593.67940375
678.44501600
769.82889499
868.05164961
973.34910317
1085.97392347
1206.19749447
1334.31207581
1470.63330792
1615...

result:

ok 47 numbers

Test #7:

score: 0
Accepted
time: 37ms
memory: 210712kb

input:

9 9999

output:

111.55622256
348.04926039
727.32800180
1273.19006403
2018.95211125
3014.58913972
4343.39280984
6171.94644244
9000.00000000

result:

ok 9 numbers