QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#54925#4228. Double SortKING_UT#AC ✓89ms20216kbC++201.1kb2022-10-11 17:32:362022-10-11 17:32:39

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-10-11 17:32:39]
  • 评测
  • 测评结果:AC
  • 用时:89ms
  • 内存:20216kb
  • [2022-10-11 17:32:36]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

#define rng(i,a,b) for(int i=int(a);i<int(b);i++)
#define rep(i,b) rng(i,0,b)
#define gnr(i,a,b) for(int i=int(b)-1;i>=int(a);i--)
#define per(i,b) gnr(i,0,b)

const int nmax=55;
const int mmax=10005;

using ld=long double;

ld bin[nmax][nmax];
ld dp[nmax][mmax],eq[nmax][mmax];
ld ans[mmax];

void slv(){
	int n,m;cin>>n>>m;
	m-=n;
	
	bin[0][0]=1;
	rep(i,n+1)rep(j,n+1){
		if(i)bin[i][j]+=bin[i-1][j];
		if(j)bin[i][j]+=bin[i][j-1];
	}
	rep(i,n+1)rep(j,n+1){
		rep(k,j){
			bin[i][j]*=(i+k+1);
			bin[i][j]/=(m+n)-(i+k);
		}
	}
	
	rng(i,1,n+1)dp[i][0]=bin[0][i];
	rng(i,1,n+1)rep(j,m-i+1){
		rng(k,i,n+1){
			dp[k][j+i]+=dp[i][j]*bin[i][k-i];
		}
	}
	rep(i,m+1)eq[n][i]=1;
	gnr(i,1,n+1)per(j,m-i+1){
		rng(k,i,n+1){
			eq[i][j]+=eq[k][j+i]*bin[i][k-i];
		}
	}
	rng(i,1,n+1)rep(j,m-i+1){
		ld w=0;
		rng(k,i,n+1){
			w+=eq[k][j+i]*bin[i][k-i];
		}
		ans[n-i]+=w*dp[i][j];
	}
	rep(i,n-1)ans[i+1]+=ans[i];
	rep(i,n)ans[i]+=1;
	rep(i,n-1)ans[i+1]+=ans[i];
	
	rep(i,n)cout<<ans[i]<<endl;
}

signed main(){
	cin.tie(0);
	ios::sync_with_stdio(0);
	cout<<fixed<<setprecision(20);
	
	slv();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 4ms
memory: 7876kb

input:

3 5

output:

1.00000000000000000000
2.29999999999999999996
4.50000000000000000000

result:

ok 3 numbers

Test #2:

score: 0
Accepted
time: 3ms
memory: 7832kb

input:

5 17

output:

1.13138332255979314801
2.74838396897220426643
5.18309631544925662576
8.85568842921784098263
15.00000000000000000000

result:

ok 5 numbers

Test #3:

score: 0
Accepted
time: 89ms
memory: 20216kb

input:

50 10000

output:

4.43281643353642924605
12.83659686678624083783
25.31526873389660153499
41.95561123829224818571
62.84807606175868663692
88.08715467575721323745
117.77163377880214473192
152.00489477779716000760
190.89524200357733471622
234.55626292508845626150
283.10722438472381543018
336.67350947320454665479
395.387...

result:

ok 50 numbers

Test #4:

score: 0
Accepted
time: 6ms
memory: 7944kb

input:

40 40

output:

1.00000000000000000000
2.00000000000000000000
3.00000000000000000000
4.00000000000000000000
5.00000000000000000000
6.00000000000000000000
7.00000000000000000000
8.00000000000000000000
9.00000000000000000000
10.00000000000000000000
11.00000000000000000000
12.00000000000000000000
13.000000000000000000...

result:

ok 40 numbers

Test #5:

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

input:

39 1489

output:

1.52708756282063701139
3.93901256521392071253
7.34033024352952002348
11.76349374502898187302
17.23670136296627585469
23.79071092050161145316
31.45828771293961443299
40.27423309031799695049
50.27559104731479331166
61.50187530303240297791
73.99532469669294276748
87.80119512643682561787
102.96809477877...

result:

ok 39 numbers

Test #6:

score: 0
Accepted
time: 81ms
memory: 19660kb

input:

47 9871

output:

4.88391758536628627432
14.20932202164489387575
28.09393480587513489827
46.64143097166726158534
69.96023578068731913621
98.16395174340850385969
131.37172304640639923512
169.70865107326744256055
213.30625266305588266791
262.30296659374342857496
316.84471482048952131749
377.08552607374023171727
443.188...

result:

ok 47 numbers

Test #7:

score: 0
Accepted
time: 6ms
memory: 7868kb

input:

9 9999

output:

111.55622255525582869201
348.04926039447652430514
727.32800179855393879480
1273.19006403006417071921
2018.95211125406978980301
3014.58913971869464187847
4343.39280983747847253440
6171.94644243750076917365
9000.00000000000000266454

result:

ok 9 numbers