QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#63514#4228. Double SortnamelessguguguAC ✓56ms18080kbC++141.3kb2022-11-22 14:44:122022-11-22 14:44:14

Judging History

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

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

answer

#include <cstdio>
#include <cstring>
#include <algorithm>
#define FILEIO(filename) (freopen(filename ".in", "r", stdin), freopen(filename ".out", "w", stdout))
typedef long long ll;
const int N = 55, M = 10005;
int n, m;
ll binom[N][N];
long double tr[N][N], f[N][M], g[N][M], sum[N];
int main(void)
{
	scanf("%d%d", &n, &m);
	for(int i = 0;i <= n;++i)
	{
		binom[i][0] = 1;
		for(int j = 1;j <= i;++j)
			binom[i][j] = binom[i - 1][j] + binom[i - 1][j - 1];
	}
	for(int i = 0;i <= n;++i)
		for(int j = i;j <= n;++j)
		{
			tr[i][j] = binom[j][i];
			for(int k = i + 1;k <= j;++k)
				tr[i][j] = tr[i][j] * k / (m - k + 1);
		}
	f[0][0] = 1;
	for(int i = 0;i <= n;++i)
		for(int j = std::max(i, 1);j <= n;++j)
			for(int k = 0;k <= m - j;++k)
				f[j][k + j] += tr[i][j] * f[i][k];
	for(int i = 0;i <= m;++i)
		g[n][i] = 1;
	for(int i = n;i >= 0;--i)
		for(int j = i;j > 0;--j)
			for(int k = m;k >= i;--k)
				g[j][k - i] += tr[j][i] * g[i][k];
	for(int i = 1;i <= n;++i)
		for(int j = 0;j <= m;++j)
			sum[i] += f[i][j] * g[i][j];
	for(int i = n;i >= 1;--i)
		sum[i] += sum[i + 1];
	std::reverse(sum + 1, sum + 1 + n);
	for(int i = 1;i <= n;++i)
		sum[i] += sum[i - 1];
	for(int i = 1;i <= n;++i)
		printf("%.9Lf%c", sum[i], " \n"[i == n]);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 3612kb

input:

3 5

output:

1.000000000 2.300000000 4.500000000

result:

ok 3 numbers

Test #2:

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

input:

5 17

output:

1.131383323 2.748383969 5.183096315 8.855688429 15.000000000

result:

ok 5 numbers

Test #3:

score: 0
Accepted
time: 56ms
memory: 18080kb

input:

50 10000

output:

4.432816434 12.836596867 25.315268734 41.955611238 62.848076062 88.087154676 117.771633779 152.004894778 190.895242004 234.556262925 283.107224385 336.673509473 395.387100391 459.387113513 528.820393899 603.842177757 684.616832836 771.318688568 864.132969973 963.256852072 1068.900654888 1181.2892032...

result:

ok 50 numbers

Test #4:

score: 0
Accepted
time: 2ms
memory: 6040kb

input:

40 40

output:

1.000000000 2.000000000 3.000000000 4.000000000 5.000000000 6.000000000 7.000000000 8.000000000 9.000000000 10.000000000 11.000000000 12.000000000 13.000000000 14.000000000 15.000000000 16.000000000 17.000000000 18.000000000 19.000000000 20.000000000 21.000000000 22.000000000 23.000000000 24.0000000...

result:

ok 40 numbers

Test #5:

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

input:

39 1489

output:

1.527087563 3.939012565 7.340330244 11.763493745 17.236701363 23.790710921 31.458287713 40.274233090 50.275591047 61.501875303 73.995324697 87.801195126 102.968094779 119.548370932 137.598558645 157.179904233 178.358979779 201.208409370 225.807733676 252.244447433 280.615255348 311.027607097 343.601...

result:

ok 39 numbers

Test #6:

score: 0
Accepted
time: 54ms
memory: 17600kb

input:

47 9871

output:

4.883917585 14.209322022 28.093934806 46.641430972 69.960235781 98.163951743 131.371723046 169.708651073 213.306252663 262.302966594 316.844714820 377.085526074 443.188230726 515.325237406 593.679403751 678.445016001 769.828894992 868.051649614 973.349103166 1085.973923466 1206.197494468 1334.312075...

result:

ok 47 numbers

Test #7:

score: 0
Accepted
time: 5ms
memory: 5372kb

input:

9 9999

output:

111.556222555 348.049260394 727.328001799 1273.190064030 2018.952111254 3014.589139719 4343.392809837 6171.946442438 9000.000000000

result:

ok 9 numbers