QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#577351 | #9300. So Many Possibilities... | huaxiamengjin | RE | 0ms | 10292kb | C++20 | 1.5kb | 2024-09-20 10:39:36 | 2024-09-20 10:39:38 |
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))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";
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 10292kb
input:
2 2 2 2
output:
0.500000000000
result:
ok found '0.5000000000', expected '0.5000000000', error '0'
Test #2:
score: -100
Runtime Error
input:
3 3 1 2 3