QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#577351#9300. So Many Possibilities...huaxiamengjinRE 0ms10292kbC++201.5kb2024-09-20 10:39:362024-09-20 10:39:38

Judging History

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

  • [2024-09-20 10:39:38]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:10292kb
  • [2024-09-20 10:39:36]
  • 提交

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

output:


result: