QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#885459#4228. Double SortjryggsAC ✓868ms441808kbC++141.6kb2025-02-06 15:44:322025-02-06 15:44:32

Judging History

This is the latest submission verdict.

  • [2025-02-06 15:44:32]
  • Judged
  • Verdict: AC
  • Time: 868ms
  • Memory: 441808kb
  • [2025-02-06 15:44:32]
  • Submitted

answer

#include <bits/stdc++.h>
using namespace std;
const int N=55,M=1e4+5;
#pragma GCC optimize("Ofast","inline","-ffast-math")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
inline int read(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	return x*f;
}
int n,m;
double jie[M],inv[M],f[N][M][2],g[N][M][N][2];
int main(){
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	n=read(),m=read();
	jie[0]=inv[0]=1;
	for(int i = 1;i<=n;i++)jie[i]=jie[i-1]*i,inv[i]=inv[i-1]/i;
	f[0][0][1]=jie[n];
	for(int i = 0;i<=n;i++){
		for(int j = i;j<=m;j++){
			if(f[i][j]==0)continue;
			if(i&&i+j<=m){
				f[i][i+j][1]=(f[i][i+j][1]+f[i][j][0]+f[i][j][1]);
				for(int k = 1;k<=i;k++)g[i][j+i][k][1]=(g[i][i+j][k][1]+g[i][j][k][0]+f[i][j][0]+g[i][j][k][1]+f[i][j][1]);
			}
			for(int l = 1;l+i<=n;l++){
				double w=f[i][j][1]*inv[l];
				f[i+l][j+l][0]=(f[i+l][j+l][0]+w);
				for(int k = i+1;k<=i+l;k++)g[i+l][j+l][k][0]=(g[i+l][j+l][k][0]+w);
			}
			for(int k = 1;k<=i;k++){
				for(int l = 1;l+i<=n;l++)g[i+l][j+l][k][0]=(g[i+l][j+l][k][0]+g[i][j][k][1]*inv[l]);
			}
		}
	}
	long double ans=0,val=0;
	for(int i = n;i<=m;i++){
		long double now = 1;
		for(int j = n;j<=i-1;j++)now*=j*1.0/(j-n+1);
		val+=now;
	}
	for(int i = n;i>=1;i--){
		for(int j = n;j<=m;j++){
			ans=(ans+g[n][j][i][0]+g[n][j][i][1]);
			// if(i==n)cout<<"!"<<j<<' '<<i<<' '<<g[n][j][i][0]+g[n][j][i][1]<<endl;
		}
		// cerr<<ans<<' '<<val<<endl;
		printf("%.7Lf\n",ans/val);
	}
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 5972kb

input:

3 5

output:

1.0000000
2.3000000
4.5000000

result:

ok 3 numbers

Test #2:

score: 0
Accepted
time: 1ms
memory: 5976kb

input:

5 17

output:

1.1313833
2.7483840
5.1830963
8.8556884
15.0000000

result:

ok 5 numbers

Test #3:

score: 0
Accepted
time: 868ms
memory: 441808kb

input:

50 10000

output:

4.4328164
12.8365969
25.3152687
41.9556112
62.8480761
88.0871547
117.7716338
152.0048948
190.8952420
234.5562629
283.1072244
336.6735095
395.3871004
459.3871135
528.8203939
603.8421778
684.6168328
771.3186886
864.1329700
963.2568521
1068.9006549
1181.2892033
1300.6633810
1427.2819151
1561.4234346
17...

result:

ok 50 numbers

Test #4:

score: 0
Accepted
time: 0ms
memory: 7632kb

input:

40 40

output:

1.0000000
2.0000000
3.0000000
4.0000000
5.0000000
6.0000000
7.0000000
8.0000000
9.0000000
10.0000000
11.0000000
12.0000000
13.0000000
14.0000000
15.0000000
16.0000000
17.0000000
18.0000000
19.0000000
20.0000000
21.0000000
22.0000000
23.0000000
24.0000000
25.0000000
26.0000000
27.0000000
28.0000000
2...

result:

ok 40 numbers

Test #5:

score: 0
Accepted
time: 39ms
memory: 56660kb

input:

39 1489

output:

1.5270876
3.9390126
7.3403302
11.7634937
17.2367014
23.7907109
31.4582877
40.2742331
50.2755910
61.5018753
73.9953247
87.8011951
102.9680948
119.5483709
137.5985586
157.1799042
178.3589798
201.2084094
225.8077337
252.2444474
280.6152553
311.0276071
343.6015935
378.4723167
415.7928925
455.7383104
498...

result:

ok 39 numbers

Test #6:

score: 0
Accepted
time: 758ms
memory: 411348kb

input:

47 9871

output:

4.8839176
14.2093220
28.0939348
46.6414310
69.9602358
98.1639517
131.3717230
169.7086511
213.3062527
262.3029666
316.8447148
377.0855261
443.1882307
515.3252374
593.6794038
678.4450160
769.8288950
868.0516496
973.3491032
1085.9739235
1206.1974945
1334.3120758
1470.6333079
1615.5031346
1769.2932338
1...

result:

ok 47 numbers

Test #7:

score: 0
Accepted
time: 75ms
memory: 84528kb

input:

9 9999

output:

111.5562226
348.0492604
727.3280018
1273.1900640
2018.9521113
3014.5891397
4343.3928098
6171.9464424
9000.0000000

result:

ok 9 numbers