QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#502780#4228. Double SortZhouShangAC ✓336ms241552kbC++201.3kb2024-08-03 13:50:512024-08-03 13:50:51

Judging History

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

  • [2024-08-03 13:50:51]
  • 评测
  • 测评结果:AC
  • 用时:336ms
  • 内存:241552kb
  • [2024-08-03 13:50:51]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
#define rep(i,a,b) for (int i = a; i < (b); i++)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define PB push_back
#define FS first
#define SD second
#define ary(k) array<int, k>
template<class A, class B> void cmx(A &x, B y) { x = max<A>(x, y);}
template<class A, class B> void cmn(A &x, B y) { x = min<A>(x, y);}
typedef pair<int, int> pii;
typedef vector<int> vi;
int n,m;
double c[10009][59],f[59][10009][59];
double C(int n,int m){
    if(!(0<=n&&n<=10000&&0<=m&&m<=50))
        return 0;
    return c[n][m];
}
signed main() {
    //cin.tie(0)->sync_with_stdio(0); cin.exceptions(cin.failbit);
    cin>>n>>m;
    for(int i=0;i<=10000;i++)
        for(int j=0;j<=min(50ll,i);j++)
            c[i][j]=!j?1:c[i-1][j]+c[i-1][j-1];
    for(int i=1;i<=n;i++)
        for(int j=i;j<=m;j++){
            for(int k=1;k<=i;k++)
                f[i][j][k]=k;
            for(int k=0;k<=i;k++){
                double p=1.0*C(j-i,k)*C(i,k)/C(j,i);
                if(p==0)
                    continue;
                for(int l=1;l<=k;l++)
                    f[i][j][i-k+l]+=p*f[k][j-i][l];
            }
        }
    for(int i=1;i<=n;i++)
        cout<<fixed<<setprecision(9)<<f[n][m][i]<<'\n';
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

3 5

output:

1.000000000
2.300000000
4.500000000

result:

ok 3 numbers

Test #2:

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

input:

5 17

output:

1.131383323
2.748383969
5.183096315
8.855688429
15.000000000

result:

ok 5 numbers

Test #3:

score: 0
Accepted
time: 336ms
memory: 241552kb

input:

50 10000

output:

4.432816434
12.836596867
25.315268734
41.955611238
62.848076062
88.087154676
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.900654888
1181.2892032...

result:

ok 50 numbers

Test #4:

score: 0
Accepted
time: 3ms
memory: 92672kb

input:

40 40

output:

1.000000000
2.000000000
3.000000000
4.000000000
5.000000000
6.000000000
7.000000000
8.000000000
9.000000000
10.000000000
11.000000000
12.000000000
13.000000000
14.000000000
15.000000000
16.000000000
17.000000000
18.000000000
19.000000000
20.000000000
21.000000000
22.000000000
23.000000000
24.0000000...

result:

ok 40 numbers

Test #5:

score: 0
Accepted
time: 16ms
memory: 117016kb

input:

39 1489

output:

1.527087563
3.939012565
7.340330244
11.763493745
17.236701363
23.790710921
31.458287713
40.274233090
50.275591047
61.501875303
73.995324697
87.801195126
102.968094779
119.548370932
137.598558645
157.179904233
178.358979779
201.208409370
225.807733676
252.244447433
280.615255348
311.027607097
343.601...

result:

ok 39 numbers

Test #6:

score: 0
Accepted
time: 278ms
memory: 226996kb

input:

47 9871

output:

4.883917585
14.209322022
28.093934806
46.641430972
69.960235781
98.163951743
131.371723046
169.708651073
213.306252663
262.302966594
316.844714820
377.085526074
443.188230726
515.325237406
593.679403751
678.445016001
769.828894992
868.051649614
973.349103166
1085.973923466
1206.197494468
1334.312075...

result:

ok 47 numbers

Test #7:

score: 0
Accepted
time: 13ms
memory: 51460kb

input:

9 9999

output:

111.556222555
348.049260394
727.328001799
1273.190064030
2018.952111254
3014.589139719
4343.392809837
6171.946442438
9000.000000000

result:

ok 9 numbers