QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#854071 | #4228. Double Sort | Schur | AC ✓ | 40ms | 19808kb | C++17 | 1.3kb | 2025-01-11 21:15:43 | 2025-01-11 21:15:43 |
Judging History
answer
#include <stdio.h>
#include <iostream>
#include <iomanip>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx2")
using namespace std;
int N, M;
long double cnt = 0;
long double a[51] = {0, };
long double dp[51][10001] = {{0, }, };
long double C[10001][51] = {{0, }, };
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> N >> M;
for (register int i = 0; i <= M; i++) C[i][0] = 1;
for (register int i = 1; i <= M; i++) for (register int j = 1; j <= N; j++) C[i][j] = C[i-1][j-1] + C[i-1][j];
dp[N][N] = 1;
for (register int i = N; i <= M; i++)
{
for (register int j = 1; j <= N; j++)
{
if (dp[j][i] == 0) continue;
for (register int k = 1; k <= j && i+k<=M; k++) dp[k][i+k] += dp[j][i]*C[j][k];
cnt += dp[j][i];
dp[j][i] *= C[M-i+j][j];
}
}
for (register int i = 1; i <= N; i++) for (register int j = N; j <= M; j++) a[N-i+1] += dp[i][j];
for (register int i = 1; i <= N; i++) a[i] /= cnt;
for (register int i = 2; i <= N; i++) a[i] += a[i-1];
for (register int i = 2; i <= N; i++) a[i] += a[i-1];
for (register int i = 1; i <= N; i++) cout << setprecision(15) << a[i] << "\n";
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 5832kb
input:
3 5
output:
1 2.3 4.5
result:
ok 3 numbers
Test #2:
score: 0
Accepted
time: 1ms
memory: 5968kb
input:
5 17
output:
1.13138332255979 2.7483839689722 5.18309631544926 8.85568842921784 15
result:
ok 5 numbers
Test #3:
score: 0
Accepted
time: 40ms
memory: 19808kb
input:
50 10000
output:
4.43281643353643 12.8365968667862 25.3152687338966 41.9556112382922 62.8480760617587 88.0871546757572 117.771633778802 152.004894777797 190.895242003577 234.556262925088 283.107224384724 336.673509473205 395.38710039129 459.387113512752 528.820393898798 603.842177756985 684.616832836495 771.31868856...
result:
ok 50 numbers
Test #4:
score: 0
Accepted
time: 0ms
memory: 5944kb
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: 2ms
memory: 7820kb
input:
39 1489
output:
1.52708756282064 3.93901256521392 7.34033024352952 11.763493745029 17.2367013629663 23.7907109205016 31.4582877129396 40.274233090318 50.2755910473148 61.5018753030324 73.9953246966929 87.8011951264368 102.968094778777 119.548370931501 137.598558644627 157.17990423317 178.358979778669 201.2084093700...
result:
ok 39 numbers
Test #6:
score: 0
Accepted
time: 31ms
memory: 19364kb
input:
47 9871
output:
4.88391758536629 14.2093220216449 28.0939348058751 46.6414309716673 69.9602357806873 98.1639517434085 131.371723046406 169.708651073267 213.306252663056 262.302966593743 316.84471482049 377.08552607374 443.188230725681 515.325237405686 593.679403750969 678.445016001069 769.828894991627 868.051649613...
result:
ok 47 numbers
Test #7:
score: 0
Accepted
time: 0ms
memory: 13728kb
input:
9 9999
output:
111.556222555256 348.049260394477 727.328001798554 1273.19006403006 2018.95211125407 3014.58913971869 4343.39280983748 6171.9464424375 9000
result:
ok 9 numbers