QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#44002#4228. Double Sortbulijiojiodibuliduo#AC ✓25ms7956kbPython2518b2022-08-12 08:21:062022-08-12 08:21:08

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-08-12 08:21:08]
  • 评测
  • 测评结果:AC
  • 用时:25ms
  • 内存:7956kb
  • [2022-08-12 08:21:06]
  • 提交

answer

from math import factorial as fac

n,m=map(int,raw_input().split())

def comb(n,m):
	if m<0 or m>n:
		return 0
	else:
		return fac(n)/fac(m)/fac(n-m)
tmp=[0]*(n+1)
f=[0]*(m+1)
for i in range(n,m+1):
	if i==n:
		f[i]=1
	else:
		f[i]=f[i-1]*i/(i-n)

for j in range(1,n+1):
	for i in range(0,m,j):
		tmp[j]+=f[m-i]

def calc(k,n,m):
	return sum(comb(n,j)*(-1)**(j-k)*comb(j-1,k-1)*tmp[j] for j in range(k,n+1))

ans=0
for i in range(1,n+1):
	ans+=1.*calc(n+1-i,n,m)/f[m]
	print "%.10f" %(ans)

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 12ms
memory: 6916kb

input:

3 5

output:

1.0000000000
2.3000000000
4.5000000000

result:

ok 3 numbers

Test #2:

score: 0
Accepted
time: 8ms
memory: 6756kb

input:

5 17

output:

1.1313833226
2.7483839690
5.1830963154
8.8556884292
15.0000000000

result:

ok 5 numbers

Test #3:

score: 0
Accepted
time: 25ms
memory: 7956kb

input:

50 10000

output:

4.4328164335
12.8365968668
25.3152687339
41.9556112383
62.8480760618
88.0871546758
117.7716337788
152.0048947778
190.8952420036
234.5562629251
283.1072243847
336.6735094732
395.3871003913
459.3871135128
528.8203938988
603.8421777570
684.6168328365
771.3186885683
864.1329699727
963.2568520715
1068.90...

result:

ok 50 numbers

Test #4:

score: 0
Accepted
time: 19ms
memory: 7156kb

input:

40 40

output:

1.0000000000
2.0000000000
3.0000000000
4.0000000000
5.0000000000
6.0000000000
7.0000000000
8.0000000000
9.0000000000
10.0000000000
11.0000000000
12.0000000000
13.0000000000
14.0000000000
15.0000000000
16.0000000000
17.0000000000
18.0000000000
19.0000000000
20.0000000000
21.0000000000
22.0000000000
2...

result:

ok 40 numbers

Test #5:

score: 0
Accepted
time: 23ms
memory: 7068kb

input:

39 1489

output:

1.5270875628
3.9390125652
7.3403302435
11.7634937450
17.2367013630
23.7907109205
31.4582877129
40.2742330903
50.2755910473
61.5018753030
73.9953246967
87.8011951264
102.9680947788
119.5483709315
137.5985586446
157.1799042332
178.3589797787
201.2084093701
225.8077336763
252.2444474329
280.6152553480
...

result:

ok 39 numbers

Test #6:

score: 0
Accepted
time: 25ms
memory: 7852kb

input:

47 9871

output:

4.8839175854
14.2093220216
28.0939348059
46.6414309717
69.9602357807
98.1639517434
131.3717230464
169.7086510733
213.3062526631
262.3029665937
316.8447148205
377.0855260737
443.1882307257
515.3252374057
593.6794037510
678.4450160011
769.8288949916
868.0516496140
973.3491031658
1085.9739234660
1206.1...

result:

ok 47 numbers

Test #7:

score: 0
Accepted
time: 12ms
memory: 7476kb

input:

9 9999

output:

111.5562225553
348.0492603945
727.3280017986
1273.1900640301
2018.9521112541
3014.5891397187
4343.3928098375
6171.9464424375
9000.0000000000

result:

ok 9 numbers