QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#577162#9300. So Many Possibilities...ship2077WA 97ms58000kbC++231.2kb2024-09-20 08:39:322024-09-20 08:39:33

Judging History

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

  • [2024-09-20 08:39:33]
  • 评测
  • 测评结果:WA
  • 用时:97ms
  • 内存:58000kb
  • [2024-09-20 08:39:32]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
constexpr int M=(1<<15)+5;
int n,m,lim,a[M],sum[M];
double ans,c[105][105],dp[M][105],coef[M][105];
int main(){
    scanf("%d%d",&n,&m);lim=(1<<n)-1;
    for (int i=0;i<n;i++) scanf("%d",&a[i]);
    for (int i=0;i<=m;i++)
        for (int j=c[i][0]=1;j<=i;j++)
            c[i][j]=c[i-1][j]+c[i-1][j-1];
    for (int i=dp[0][0]=1;i<=m;i++)
        dp[0][i]=dp[0][i-1]/n;
    coef[0][0]=1;
    for (int sta=1;sta<=lim;sta++){
        int low=sta&-sta,p=__builtin_ctz(sta);
        int cnt=n-__builtin_popcount(sta);
        sum[sta]=sum[sta^low]+a[p];
        for (int i=0;i<n;i++) if (sta>>i&1)
            for (int j=sum[sta];j<=m;j++)
                dp[sta][j]+=dp[sta^1<<i][j-1]/(cnt+1)*c[j-sum[sta^1<<i]-1][a[i]-1];
        for (int i=sum[sta];i<=m;i++)
            dp[sta][i]+=dp[sta][i-1]/cnt;
        for (int i=0;i<a[p];i++)
            for (int j=0;i+j<=m;j++)
                coef[sta][i+j]+=c[i+j][j]*coef[sta^low][j];
    }
    for (int sta=1;sta<=lim;sta++) if (sum[sta]<=m)
        ans+=__builtin_popcount(sta)*dp[sta][m]*coef[lim^sta][m-sum[sta]];
    printf("%.12lf\n",ans);
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

2 2
2 2

output:

0.500000000000

result:

ok found '0.5000000000', expected '0.5000000000', error '0'

Test #2:

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

input:

3 3
1 2 3

output:

1.083333333333

result:

ok found '1.0833333333', expected '1.0833333333', error '3.33289e-13'

Test #3:

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

input:

3 100
80 32 38

output:

0.917682017513

result:

ok found '0.9176820175', expected '0.9176820175', error '2.97318e-13'

Test #4:

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

input:

4 100
31 80 40 28

output:

0.389601136717

result:

ok found '0.3896011367', expected '0.3896011367', error '1.47604e-13'

Test #5:

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

input:

8 100
37 42 41 43 52 24 7 21

output:

0.996650548013

result:

ok found '0.9966505480', expected '0.9966505480', error '1.22125e-14'

Test #6:

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

input:

9 100
6 13 4 6 20 13 10 25 25

output:

5.755547655021

result:

ok found '5.7555476550', expected '5.7555476550', error '2.66454e-14'

Test #7:

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

input:

10 10
6 5 6 10 9 6 10 7 1 9

output:

0.653713647886

result:

ok found '0.6537136479', expected '0.6537136479', error '2.56684e-13'

Test #8:

score: 0
Accepted
time: 11ms
memory: 37608kb

input:

15 50
6 5 9 1 3 3 10 19 16 18 10 12 16 14 6

output:

3.038971162172

result:

ok found '3.0389711622', expected '3.0389711622', error '8.43769e-14'

Test #9:

score: 0
Accepted
time: 97ms
memory: 31676kb

input:

15 100
80 42 42 99 93 31 22 48 37 58 77 96 5 87 79

output:

0.803948374562

result:

ok found '0.8039483746', expected '0.8039483746', error '3.99902e-13'

Test #10:

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

input:

3 50
34 30 36

output:

0.000100617103

result:

ok found '0.0001006171', expected '0.0001006171', error '4.148e-13'

Test #11:

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

input:

10 90
10 11 9 10 10 8 11 13 8 9

output:

6.382627579873

result:

ok found '6.3826275799', expected '6.3826275799', error '7.99361e-15'

Test #12:

score: 0
Accepted
time: 9ms
memory: 11876kb

input:

12 100
12 13 10 11 11 14 14 10 7 8 4 8

output:

5.784451171289

result:

ok found '5.7844511713', expected '5.7844511713', error '2.14051e-13'

Test #13:

score: 0
Accepted
time: 35ms
memory: 57356kb

input:

15 100
12 11 12 10 15 12 7 6 12 5 11 7 10 11 9

output:

3.850874013381

result:

ok found '3.8508740134', expected '3.8508740134', error '2.72227e-13'

Test #14:

score: 0
Accepted
time: 39ms
memory: 58000kb

input:

15 100
7 7 6 4 11 8 12 8 5 7 9 8 10 8 15

output:

7.813084239524

result:

ok found '7.8130842395', expected '7.8130842395', error '2.57572e-13'

Test #15:

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

input:

10 95
8 11 6 14 6 5 11 14 10 14

output:

8.138051491019

result:

ok found '8.1380514910', expected '8.1380514910', error '1.77636e-13'

Test #16:

score: 0
Accepted
time: 4ms
memory: 11660kb

input:

12 93
4 8 6 8 12 8 10 6 8 8 13 9

output:

9.120009675931

result:

ok found '9.1200096759', expected '9.1200096759', error '5.15143e-14'

Test #17:

score: 0
Accepted
time: 46ms
memory: 57844kb

input:

15 99
9 5 8 4 9 7 4 6 7 7 5 6 8 8 7

output:

14.000000000000

result:

ok found '14.0000000000', expected '14.0000000000', error '5.32907e-15'

Test #18:

score: -100
Wrong Answer
time: 29ms
memory: 57936kb

input:

15 88
6 3 8 4 5 6 6 5 10 6 4 7 8 3 7

output:

-nan

result:

wrong output format Expected double, but "-nan" found