QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#63514 | #4228. Double Sort | namelessgugugu | AC ✓ | 56ms | 18080kb | C++14 | 1.3kb | 2022-11-22 14:44:12 | 2022-11-22 14:44:14 |
Judging History
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