QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #577376 | #9300. So Many Possibilities... | huaxiamengjin | AC ✓ | 1091ms | 68152kb | C++20 | 1.5kb | 2024-09-20 10:51:06 | 2024-09-20 10:51:06 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
int n,m;
double p[100100],ni[100100];
int a[100100];
double f[40100][110];
double sf[40100][110];
double g[40100][110];
double ans,c[1010][1010];
int main(){
cin>>n>>m;
for (int i=0;i<n;i++)
cin>>a[i];
c[0][0]=1;
for (int i=1;i<=m;i++){
c[i][0]=1;
for (int j=1;j<=m;j++)
c[i][j]=c[i-1][j]+c[i-1][j-1];
}
int nn=1<<n;
f[0][0]=1;
for (int i=0;i<nn;i++){
int tmp=__builtin_popcount(i);
if(n==tmp)continue;
sf[i][0]=f[i][0];
for (int j=1;j<=m;j++)
sf[i][j]=sf[i][j-1]*(1.0/(n-tmp))+f[i][j];
int sum=0;
for (int ii=0;ii<n;ii++)
if(i>>ii&1)sum+=a[ii];
for (int k=1;k<=m;k++)
for (int ii=0;ii<n;ii++)
if((!(i>>ii&1))&&k-sum-1>=0)f[i|(1<<ii)][k]+=sf[i][k-1]*(1.0/(n-tmp))*c[k-sum-1][a[ii]-1];
}
// cout<<"&&&&\n";
for (int i=0;i<nn;i++){
int pre=0;
g[0][0]=1;
for (int ii=0;ii<n;ii++)
if(!(i>>ii&1)){
// cout<<"!!!\n";
pre++;
for (int k=m;~k;k--){
g[pre][k]=0;
for (int j=max(k-a[ii]+1,0);j<=k;j++)
g[pre][k]+=g[pre-1][j]*c[k][j];
}
}
// cout<<"^^^\n";
int tmp=__builtin_popcount(i);
double sum=0;int sum2=0;
// if(n==tmp)cout<<"&&&&&\n";
for (int j=0;j<=m;j++)sum=((n==tmp)?0:sum*(1.0/(n-tmp)))+f[i][j];
// cout<<i<<" "<<j<<" "<<f[i][j]<<"\n";
// cout<<i<<" "<<sum<<"\n";
for (int ii=0;ii<n;ii++)
if(i>>ii&1)sum2+=a[ii];
if(sum2>m)continue;
// cout<<sum2<<"&&&"<<g[pre][m-sum2]<<"\n";
ans+=sum*g[pre][m-sum2]*tmp;
}
printf("%.12lf\n",ans);
// cout<<ans<<"\n";
}
这程序好像有点Bug，我给组数据试试？
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 10116kb
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: 9808kb
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: 10556kb
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: 0ms
memory: 10568kb
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: 3ms
memory: 10672kb
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: 4ms
memory: 12084kb
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: 10160kb
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: 117ms
memory: 51768kb
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: 771ms
memory: 40068kb
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: 2ms
memory: 10080kb
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: 6ms
memory: 10552kb
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: 24ms
memory: 16440kb
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: 233ms
memory: 64832kb
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: 221ms
memory: 67144kb
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: 7ms
memory: 14356kb
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: 19ms
memory: 14188kb
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: 196ms
memory: 65800kb
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: 169ms
memory: 66624kb
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: 1ms
memory: 9904kb
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: 12ms
memory: 12416kb
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: 658ms
memory: 37148kb
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: 10304kb
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: 3ms
memory: 11204kb
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: 13ms
memory: 12688kb
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: 31ms
memory: 18172kb
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: 34ms
memory: 17512kb
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: 86ms
memory: 25100kb
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: 467ms
memory: 47256kb
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: 530ms
memory: 43572kb
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: 7ms
memory: 13388kb
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: 17ms
memory: 18784kb
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: 47ms
memory: 39400kb
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: 175ms
memory: 64932kb
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: 273ms
memory: 64740kb
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: 665ms
memory: 38344kb
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: 216ms
memory: 68152kb
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: 1091ms
memory: 39272kb
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