QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#854071#4228. Double SortSchurAC ✓40ms19808kbC++171.3kb2025-01-11 21:15:432025-01-11 21:15:43

Judging History

This is the latest submission verdict.

  • [2025-01-11 21:15:43]
  • Judged
  • Verdict: AC
  • Time: 40ms
  • Memory: 19808kb
  • [2025-01-11 21:15:43]
  • Submitted

answer

#include <stdio.h>
#include <iostream>
#include <iomanip>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx2")
using namespace std;

int N, M;
long double cnt = 0;
long double a[51] = {0, };
long double dp[51][10001] = {{0, }, };
long double C[10001][51] = {{0, }, };

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> N >> M;
    for (register int i = 0; i <= M; i++) C[i][0] = 1;
    for (register int i = 1; i <= M; i++) for (register int j = 1; j <= N; j++) C[i][j] = C[i-1][j-1] + C[i-1][j];
    dp[N][N] = 1;
    for (register int i = N; i <= M; i++)
    {
        for (register int j = 1; j <= N; j++)
        {
            if (dp[j][i] == 0) continue;
            for (register int k = 1; k <= j && i+k<=M; k++) dp[k][i+k] += dp[j][i]*C[j][k];
            cnt += dp[j][i];
            dp[j][i] *= C[M-i+j][j];
        }
    }
    for (register int i = 1; i <= N; i++) for (register int j = N; j <= M; j++) a[N-i+1] += dp[i][j];
    for (register int i = 1; i <= N; i++) a[i] /= cnt;
    for (register int i = 2; i <= N; i++) a[i] += a[i-1];
    for (register int i = 2; i <= N; i++) a[i] += a[i-1];
    for (register int i = 1; i <= N; i++) cout << setprecision(15) << a[i] << "\n";
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 5832kb

input:

3 5

output:

1
2.3
4.5

result:

ok 3 numbers

Test #2:

score: 0
Accepted
time: 1ms
memory: 5968kb

input:

5 17

output:

1.13138332255979
2.7483839689722
5.18309631544926
8.85568842921784
15

result:

ok 5 numbers

Test #3:

score: 0
Accepted
time: 40ms
memory: 19808kb

input:

50 10000

output:

4.43281643353643
12.8365968667862
25.3152687338966
41.9556112382922
62.8480760617587
88.0871546757572
117.771633778802
152.004894777797
190.895242003577
234.556262925088
283.107224384724
336.673509473205
395.38710039129
459.387113512752
528.820393898798
603.842177756985
684.616832836495
771.31868856...

result:

ok 50 numbers

Test #4:

score: 0
Accepted
time: 0ms
memory: 5944kb

input:

40 40

output:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

result:

ok 40 numbers

Test #5:

score: 0
Accepted
time: 2ms
memory: 7820kb

input:

39 1489

output:

1.52708756282064
3.93901256521392
7.34033024352952
11.763493745029
17.2367013629663
23.7907109205016
31.4582877129396
40.274233090318
50.2755910473148
61.5018753030324
73.9953246966929
87.8011951264368
102.968094778777
119.548370931501
137.598558644627
157.17990423317
178.358979778669
201.2084093700...

result:

ok 39 numbers

Test #6:

score: 0
Accepted
time: 31ms
memory: 19364kb

input:

47 9871

output:

4.88391758536629
14.2093220216449
28.0939348058751
46.6414309716673
69.9602357806873
98.1639517434085
131.371723046406
169.708651073267
213.306252663056
262.302966593743
316.84471482049
377.08552607374
443.188230725681
515.325237405686
593.679403750969
678.445016001069
769.828894991627
868.051649613...

result:

ok 47 numbers

Test #7:

score: 0
Accepted
time: 0ms
memory: 13728kb

input:

9 9999

output:

111.556222555256
348.049260394477
727.328001798554
1273.19006403006
2018.95211125407
3014.58913971869
4343.39280983748
6171.9464424375
9000

result:

ok 9 numbers