QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#212445#4228. Double Sortopen your brain (Zhi Zhang, Yanru Guan, Jianfeng Zhu)#AC ✓2ms3904kbC++141.0kb2023-10-13 15:57:462023-10-13 15:57:46

Judging History

This is the latest submission verdict.

  • [2023-10-13 15:57:46]
  • Judged
  • Verdict: AC
  • Time: 2ms
  • Memory: 3904kb
  • [2023-10-13 15:57:46]
  • Submitted

answer

#include <bits/stdc++.h>

using namespace std;

typedef __float128 f128;

int n, m;
long long c[55][55];
f128 val[10005], ans[55], v[55];

int main() {
    cin >> n >> m;
    val[0] = 1;
    for (int i = 1; i <= m - n; i++) {
        val[i] = val[i - 1] * (m - n - i + 1) / (m - i + 1);
    }
    for (int i = 0; i <= n; i++) {
        c[i][0] = c[i][i] = 1;
        for (int j = 1; j < i; j++) {
            c[i][j] = c[i - 1][j - 1] + c[i - 1][j];
        }
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j * i + n - i <= m; j++) {
            v[i] += val[i * (j - 1)];
        }
    }

    for (int k = 1; k <= n; k++) {
        for (int j = k; j <= n; j++) {
            int fg = (j - k) % 2 ? -1 : 1;
            ans[k] += fg * c[n][j] * v[j] * c[j - 1][k - 1];
        }
    }

    reverse(ans + 1, ans + n + 1);
    for (int i = 2; i <= n; i++) {
        ans[i] += ans[i - 1];
    }
    for (int i = 1; i <= n; i++) {
        cout << fixed << setprecision(10) << (long double)ans[i] << endl;
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3672kb

input:

3 5

output:

1.0000000000
2.3000000000
4.5000000000

result:

ok 3 numbers

Test #2:

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

input:

5 17

output:

1.1313833226
2.7483839690
5.1830963154
8.8556884292
15.0000000000

result:

ok 5 numbers

Test #3:

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

input:

50 10000

output:

4.4328164335
12.8365968668
25.3152687339
41.9556112383
62.8480760618
88.0871546758
117.7716337788
152.0048947778
190.8952420036
234.5562629251
283.1072243847
336.6735094732
395.3871003913
459.3871135128
528.8203938988
603.8421777570
684.6168328365
771.3186885683
864.1329699727
963.2568520715
1068.90...

result:

ok 50 numbers

Test #4:

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

input:

40 40

output:

1.0000000000
2.0000000000
3.0000000000
4.0000000000
5.0000000000
6.0000000000
7.0000000000
8.0000000000
9.0000000000
10.0000000000
11.0000000000
12.0000000000
13.0000000000
14.0000000000
15.0000000000
16.0000000000
17.0000000000
18.0000000000
19.0000000000
20.0000000000
21.0000000000
22.0000000000
2...

result:

ok 40 numbers

Test #5:

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

input:

39 1489

output:

1.5270875628
3.9390125652
7.3403302435
11.7634937450
17.2367013630
23.7907109205
31.4582877129
40.2742330903
50.2755910473
61.5018753030
73.9953246967
87.8011951264
102.9680947788
119.5483709315
137.5985586446
157.1799042332
178.3589797787
201.2084093701
225.8077336763
252.2444474329
280.6152553480
...

result:

ok 39 numbers

Test #6:

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

input:

47 9871

output:

4.8839175854
14.2093220216
28.0939348059
46.6414309717
69.9602357807
98.1639517434
131.3717230464
169.7086510733
213.3062526631
262.3029665937
316.8447148205
377.0855260737
443.1882307257
515.3252374057
593.6794037510
678.4450160011
769.8288949916
868.0516496140
973.3491031658
1085.9739234660
1206.1...

result:

ok 47 numbers

Test #7:

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

input:

9 9999

output:

111.5562225553
348.0492603945
727.3280017986
1273.1900640301
2018.9521112541
3014.5891397187
4343.3928098375
6171.9464424375
9000.0000000000

result:

ok 9 numbers