QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#577180#9300. So Many Possibilities...ship2077AC ✓130ms58056kbC++231.2kb2024-09-20 08:51:252024-09-20 08:51:26

Judging History

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

  • [2024-09-20 08:51:26]
  • 评测
  • 测评结果：AC
  • 用时：130ms
  • 内存：58056kb
查看
  • [2024-09-20 08:51:25]
  • 提交

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]+1;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;
}
源文件, 语言: C++23

这程序好像有点Bug，我给组数据试试？

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 6112kb

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: 8160kb

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

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: 6208kb

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

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

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

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

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

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: 5868kb

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

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

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

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

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

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

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

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: 0
Accepted
time: 34ms
memory: 57740kb

input:

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

output:

15.000000000000

result:

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

Test #19:

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

input:

5 10
18 68 13 47 14

output:

0.000000000000

result:

ok found '0.0000000000', expected '0.0000000000', error '0'

Test #20:

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

input:

10 80
92 91 100 87 88 88 100 87 94 93

output:

0.000000000000

result:

ok found '0.0000000000', expected '0.0000000000', error '0'

Test #21:

score: 0
Accepted
time: 77ms
memory: 32268kb

input:

15 80
93 87 84 83 91 95 83 84 98 93 88 95 81 92 99

output:

0.000000000000

result:

ok found '0.0000000000', expected '0.0000000000', error '0'

Test #22:

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

input:

5 100
14 89 6 98 11

output:

2.999741338238

result:

ok found '2.9997413382', expected '2.9997413382', error '3.72147e-13'

Test #23:

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

input:

10 100
1 5 4 1 5 4 2 87 3 4

output:

9.000000000000

result:

ok found '9.0000000000', expected '9.0000000000', error '0'

Test #24:

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

input:

10 95
85 89 36 9 18 3 13 23 11 36

output:

2.479363246346

result:

ok found '2.4793632463', expected '2.4793632463', error '1.17684e-13'

Test #25:

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

input:

12 94
1 80 8 83 8 10 5 6 10 12 84 2

output:

7.643512335803

result:

ok found '7.6435123358', expected '7.6435123358', error '1.93623e-13'

Test #26:

score: 0
Accepted
time: 14ms
memory: 11300kb

input:

12 93
81 83 1 1 1 1 1 1 1 1 78 1

output:

8.999999999784

result:

ok found '8.9999999998', expected '8.9999999998', error '8.88178e-15'

Test #27:

score: 0
Accepted
time: 8ms
memory: 15492kb

input:

13 92
5 85 5 76 2 3 5 1 3 74 80 2 2

output:

8.997191721759

result:

ok found '8.9971917218', expected '8.9971917218', error '1.59872e-13'

Test #28:

score: 0
Accepted
time: 55ms
memory: 34604kb

input:

15 91
82 12 8 72 12 6 4 7 3 9 9 78 91 75 90

output:

3.900302178708

result:

ok found '3.9003021787', expected '3.9003021787', error '4.44089e-14'

Test #29:

score: 0
Accepted
time: 31ms
memory: 33300kb

input:

15 90
1 85 7 77 14 5 87 88 7 78 82 7 11 73 79

output:

3.356495973680

result:

ok found '3.3564959737', expected '3.3564959737', error '1.82965e-13'

Test #30:

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

input:

11 85
1 1 1 1 20 4 1 11 55 4 1

output:

9.996884736322

result:

ok found '9.9968847363', expected '9.9968847363', error '1.1191e-13'

Test #31:

score: 0
Accepted
time: 7ms
memory: 12776kb

input:

12 80
5 2 3 2 1 6 2 23 5 1 24 16

output:

9.932851819787

result:

ok found '9.9328518198', expected '9.9328518198', error '3.76588e-13'

Test #32:

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

input:

14 50
14 5 1 10 1 5 2 1 16 6 2 2 7 3

output:

9.351478629602

result:

ok found '9.3514786296', expected '9.3514786296', error '4.86722e-13'

Test #33:

score: 0
Accepted
time: 47ms
memory: 57864kb

input:

15 93
9 1 18 1 2 6 7 13 30 3 1 1 2 1 1

output:

13.944979596803

result:

ok found '13.9449795968', expected '13.9449795968', error '4.83169e-13'

Test #34:

score: 0
Accepted
time: 12ms
memory: 47704kb

input:

15 100
2 5 1 26 9 1 7 34 6 2 20 5 72 3 7

output:

10.819301253602

result:

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

Test #35:

score: 0
Accepted
time: 18ms
memory: 31984kb

input:

15 100
1 8 15 22 29 36 43 50 57 64 71 78 85 92 99

output:

1.416049163981

result:

ok found '1.4160491640', expected '1.4160491640', error '2.1072e-13'

Test #36:

score: 0
Accepted
time: 52ms
memory: 57872kb

input:

15 100
15 14 13 12 11 10 9 8 7 6 5 4 3 2 1

output:

9.628757344296

result:

ok found '9.6287573443', expected '9.6287573443', error '9.76996e-14'

Test #37:

score: 0
Accepted
time: 130ms
memory: 31572kb

input:

15 100
100 100 100 100 100 100 100 100 100 100 100 100 100 100 100

output:

0.000000000000

result:

ok found '0.0000000000', expected '0.0000000000', error '0'

Extra Test:

score: 0
Extra Test Passed
English 繁體中文 简体中文

服务器时间: 2024-12-04 04:45:15 | 开源项目