QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#208244#4228. Double Sortucup-team1209#AC ✓30ms14488kbC++201.6kb2023-10-09 11:52:472023-10-09 11:52:47

Judging History

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

  • [2023-10-09 11:52:47]
  • 评测
  • 测评结果:AC
  • 用时:30ms
  • 内存:14488kb
  • [2023-10-09 11:52:47]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define rep(i,x,y) for (int i=(x);i<=(y);i++)
#define drep(i,y,x) for (int i=(y);i>=(x);i--)
#define pii pair<int,int>
#define fir first
#define sec second
#define MP make_pair
template<typename T> bool chkmin(T &x,T y){return x>y?x=y,1:0;}
template<typename T> bool chkmax(T &x,T y){return x<y?x=y,1:0;}
void file() {
    #ifdef zqj
    freopen("a.in","r",stdin);
    #endif
}
typedef long long ll;
typedef __float128 db;
#define sz 10010

int n,m;
db ans[sz];
db C[sz][66]; // check size

int main() {
    file();
    cin>>n>>m;
    rep(i,0,sz-1) C[i][0]=1;
    rep(i,1,sz-1) rep(j,1,min(i,n)) C[i][j]=C[i-1][j]+C[i-1][j-1];
    // rep(k,1,n) rep(i,1,m) rep(j,0,k-1) {
    //     int mm=m-(n-j)*(i-1);
    //     if (mm<0) continue;
    //     // at most mm into n, where j of them be <i
    //     db res=0;
    //     rep(t,0,j) {
    //         int mmm=mm-t*(i-1);
    //         if (mmm<0) break;
    //         db w=((t&1)?-1:1)*C[j][t]*C[mmm][n];
    //         res+=w;
    //     }
    //     ans[k]+=res*C[n][j]/C[m][n];
    // }
    rep(k,1,n) {
        std::vector<db> val(k+1);
        rep(x,0,k-1) {
            db w1=0;
            rep(i,1,m) if ((n-x)*(i-1)<=m) w1+=C[m-(n-x)*(i-1)][n]/C[m][n];
            db w2=0;
            rep(j,0,k-x-1) w2+=(((j&1)?-1:1)*C[n-x][j]);
            val[x]=C[n][x]*w1*w2;
        }
        for(int i=0;i<k;i+=2) {
            // cout<<val[i]<<' '<<val[i+1]<<'\n';
            ans[k]+=val[i]+val[i+1];
        }
    }
    rep(i,1,n) ans[i]+=ans[i-1];
    rep(i,1,n) printf("%.10Lf\n",(long double)ans[i]);
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 3ms
memory: 14212kb

input:

3 5

output:

1.0000000000
2.3000000000
4.5000000000

result:

ok 3 numbers

Test #2:

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

input:

5 17

output:

1.1313833226
2.7483839690
5.1830963154
8.8556884292
15.0000000000

result:

ok 5 numbers

Test #3:

score: 0
Accepted
time: 28ms
memory: 14364kb

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: 8ms
memory: 14096kb

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: 10ms
memory: 14092kb

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: 30ms
memory: 14488kb

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

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