QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#577363 | #9300. So Many Possibilities... | huaxiamengjin | RE | 4ms | 12528kb | C++20 | 1.5kb | 2024-09-20 10:45:17 | 2024-09-20 10:45:17 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
int n,m;
double p[100100],ni[100100];
int a[100100];
double f[10100][110];
double sf[10100][110];
double g[10100][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";
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 10140kb
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: 9936kb
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: 10756kb
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: 10692kb
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: 10404kb
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: 12528kb
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: 12408kb
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: -100
Runtime Error
input:
15 50 6 5 9 1 3 3 10 19 16 18 10 12 16 14 6