QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#577376#9300. So Many Possibilities...huaxiamengjinAC ✓1091ms68152kbC++201.5kb2024-09-20 10:51:062024-09-20 10:51:06

Judging History

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

  • [2024-09-20 10:51:06]
  • 评测
  • 测评结果：AC
  • 用时：1091ms
  • 内存：68152kb
查看
  • [2024-09-20 10:51:06]
  • 提交

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";
}
源文件, 语言: C++20

这程序好像有点Bug，我给组数据试试？

詳細信息

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
English 繁體中文 简体中文

伺服器時間: 2024-12-11 15:43:30 | 開源專案