QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#577363#9300. So Many Possibilities...huaxiamengjinRE 4ms12528kbC++201.5kb2024-09-20 10:45:172024-09-20 10:45:17

Judging History

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

  • [2024-09-20 10:45:17]
  • 评测
  • 测评结果:RE
  • 用时:4ms
  • 内存:12528kb
  • [2024-09-20 10:45:17]
  • 提交

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

output:


result: