QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#58546#4228. Double SortxiaoyaowudiAC ✓55ms13200kbC++17854b2022-10-26 20:25:412022-10-26 20:25:42

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-26 20:25:42]
  • 评测
  • 测评结果:AC
  • 用时:55ms
  • 内存:13200kb
  • [2022-10-26 20:25:41]
  • 提交

answer

#include <iostream>
#include <algorithm>
#include <iomanip>
constexpr int M=10010,N=60;
typedef __float128 lf;
lf comb[M][N];
int main(){
	comb[0][0]=1;
	for(int i=1;i<M;++i)
	{
		comb[i][0]=1;
		for(int j=1;j<=i && j<N;++j) comb[i][j]=comb[i-1][j]+comb[i-1][j-1];
	}
	int n,m;
	std::cin>>n>>m;
	lf tot=comb[m][n];
	static lf ans[N];
	for(int i=1;i<=n;++i)
	{
		static lf G[N];
		for(int k=i;k<=n;++k)
		{
			lf cur=1;
			for(int j=i;j<k;++j) cur-=comb[k][j]*G[j];
			G[k]=cur;
		}
		for(int j=1;i*j+n-i<=m;++j)
		{
			lf cur=0;
			for(int k=i;k<=n;++k)
			{
				int sum=m-k*(j-1);
				if(sum>0) cur+=G[k]*comb[n][k]*comb[sum][n];
			}
			ans[n-i+1]+=cur/tot;
		}
	}
	std::cout<<std::setprecision(8);
	for(int i=1;i<=n;++i) ans[i]+=ans[i-1],std::cout<<(long double)ans[i]<<" ";
	std::cout<<std::endl;
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 19ms
memory: 13172kb

input:

3 5

output:

1 2.3 4.5 

result:

ok 3 numbers

Test #2:

score: 0
Accepted
time: 13ms
memory: 13048kb

input:

5 17

output:

1.1313833 2.748384 5.1830963 8.8556884 15 

result:

ok 5 numbers

Test #3:

score: 0
Accepted
time: 42ms
memory: 13108kb

input:

50 10000

output:

4.4328164 12.836597 25.315269 41.955611 62.848076 88.087155 117.77163 152.00489 190.89524 234.55626 283.10722 336.67351 395.3871 459.38711 528.82039 603.84218 684.61683 771.31869 864.13297 963.25685 1068.9007 1181.2892 1300.6634 1427.2819 1561.4234 1703.3889 1853.5042 2012.1238 2179.6341 2356.4587 2...

result:

ok 50 numbers

Test #4:

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

input:

40 40

output:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 

result:

ok 40 numbers

Test #5:

score: 0
Accepted
time: 20ms
memory: 13188kb

input:

39 1489

output:

1.5270876 3.9390126 7.3403302 11.763494 17.236701 23.790711 31.458288 40.274233 50.275591 61.501875 73.995325 87.801195 102.96809 119.54837 137.59856 157.1799 178.35898 201.20841 225.80773 252.24445 280.61526 311.02761 343.60159 378.47232 415.79289 455.73831 498.51048 544.34497 593.52016 646.37014 7...

result:

ok 39 numbers

Test #6:

score: 0
Accepted
time: 55ms
memory: 13200kb

input:

47 9871

output:

4.8839176 14.209322 28.093935 46.641431 69.960236 98.163952 131.37172 169.70865 213.30625 262.30297 316.84471 377.08553 443.18823 515.32524 593.6794 678.44502 769.82889 868.05165 973.3491 1085.9739 1206.1975 1334.3121 1470.6333 1615.5031 1769.2932 1932.4091 2105.2947 2288.4387 2482.3809 2687.7212 29...

result:

ok 47 numbers

Test #7:

score: 0
Accepted
time: 29ms
memory: 13156kb

input:

9 9999

output:

111.55622 348.04926 727.328 1273.1901 2018.9521 3014.5891 4343.3928 6171.9464 9000 

result:

ok 9 numbers