QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#73384#4228. Double SortLinsheyAC ✓73ms40720kbC++172.0kb2023-01-24 20:54:342023-01-24 20:54:37

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-01-24 20:54:37]
  • 评测
  • 测评结果:AC
  • 用时:73ms
  • 内存:40720kb
  • [2023-01-24 20:54:34]
  • 提交

answer


#include <bits/stdc++.h>

using namespace std; const int maxn = 51, maxm = 10001;

const int H = 1e9;

inline void add(vector<int> &a, const vector<int> &b)
{
    while (a.size() < b.size()) a.push_back(0);
    int x = 0;
    int i;
    for (i = 0; i < b.size(); i++)
    {
        x += a[i] + b[i];
        if (x >= H) a[i] = x - H, x = 1;
        else a[i] = x, x = 0;
        assert(a[i] < H);
    }
    while (x && i < a.size())
    {
        x += a[i];
        if (x >= H) a[i] = x - H, x = 1;
        else a[i] = x, x = 0;
        assert(a[i] < H);
        i++;
    }
    if (x) a.push_back(1); 
}

inline __float128 trans(const vector<int> &a)
{
    __float128 res = 0;
    for (int i = int(a.size()) - 1; i >= 0; i--) res = res * H + a[i];
    return res;
}

vector<int> C[maxm][maxn]; __float128 C_[maxn][maxn];

int n, m;

__float128 tot, f[maxn];

__float128 Ans;

int main()
{
    for (int i = 0; i < maxm; i++)
    {
        C[i][0] = { 1 };
        for (int j = 1; j <= i && j < maxn; j++) C[i][j] = C[i - 1][j - 1], add(C[i][j], C[i - 1][j]);
    }
    for (int i = 0; i < maxn; i++)
    {
        C_[i][0] = 1;
        for (int j = 1; j <= i && j < maxn; j++) C_[i][j] = C_[i - 1][j - 1] + C_[i - 1][j];
    }
    // cout << C_[50][25] << endl;
    // cout << trans(C[50][25]) << endl;
    // for (int x : C[50][25]) printf("%9d", x); cerr << endl;
    // return 0;
    cin >> n >> m;
    tot = trans(C[m][n]);
    // cout << tot << endl;
    for (int i = 1; i <= n; i++)
    {
        vector<int> now;
        for (int j = 0; m - i * j >= n; j++) add(now, C[m - i * j][n]);
        f[i] = trans(now) / tot;
        // cerr << f[i] << endl;
    }
    cout << setprecision(12);
    for (int k = n; k; k--)
    {
        for (int i = k; i <= n; i++)
        {
            Ans += f[i] * C_[i - 1][k - 1] * C_[n][i] * (i - k & 1 ? -1 : 1);
        }
        cout << (double)Ans << endl;
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 50ms
memory: 40560kb

input:

3 5

output:

1
2.3
4.5

result:

ok 3 numbers

Test #2:

score: 0
Accepted
time: 51ms
memory: 40720kb

input:

5 17

output:

1.13138332256
2.74838396897
5.18309631545
8.85568842922
15

result:

ok 5 numbers

Test #3:

score: 0
Accepted
time: 44ms
memory: 40624kb

input:

50 10000

output:

4.43281643354
12.8365968668
25.3152687339
41.9556112383
62.8480760618
88.0871546758
117.771633779
152.004894778
190.895242004
234.556262925
283.107224385
336.673509473
395.387100391
459.387113513
528.820393899
603.842177757
684.616832836
771.318688568
864.132969973
963.256852072
1068.90065489
1181.2...

result:

ok 50 numbers

Test #4:

score: 0
Accepted
time: 58ms
memory: 40580kb

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: 62ms
memory: 40564kb

input:

39 1489

output:

1.52708756282
3.93901256521
7.34033024353
11.763493745
17.236701363
23.7907109205
31.4582877129
40.2742330903
50.2755910473
61.501875303
73.9953246967
87.8011951264
102.968094779
119.548370932
137.598558645
157.179904233
178.358979779
201.20840937
225.807733676
252.244447433
280.615255348
311.027607...

result:

ok 39 numbers

Test #6:

score: 0
Accepted
time: 73ms
memory: 40540kb

input:

47 9871

output:

4.88391758537
14.2093220216
28.0939348059
46.6414309717
69.9602357807
98.1639517434
131.371723046
169.708651073
213.306252663
262.302966594
316.84471482
377.085526074
443.188230726
515.325237406
593.679403751
678.445016001
769.828894992
868.051649614
973.349103166
1085.97392347
1206.19749447
1334.31...

result:

ok 47 numbers

Test #7:

score: 0
Accepted
time: 62ms
memory: 40556kb

input:

9 9999

output:

111.556222555
348.049260394
727.328001799
1273.19006403
2018.95211125
3014.58913972
4343.39280984
6171.94644244
9000

result:

ok 9 numbers