QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#73384 | #4228. Double Sort | Linshey | AC ✓ | 73ms | 40720kb | C++17 | 2.0kb | 2023-01-24 20:54:34 | 2023-01-24 20:54:37 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std; const int maxn = 51, maxm = 10001;
const int H = 1e9;
inline void add(vector<int> &a, const vector<int> &b)
{
while (a.size() < b.size()) a.push_back(0);
int x = 0;
int i;
for (i = 0; i < b.size(); i++)
{
x += a[i] + b[i];
if (x >= H) a[i] = x - H, x = 1;
else a[i] = x, x = 0;
assert(a[i] < H);
}
while (x && i < a.size())
{
x += a[i];
if (x >= H) a[i] = x - H, x = 1;
else a[i] = x, x = 0;
assert(a[i] < H);
i++;
}
if (x) a.push_back(1);
}
inline __float128 trans(const vector<int> &a)
{
__float128 res = 0;
for (int i = int(a.size()) - 1; i >= 0; i--) res = res * H + a[i];
return res;
}
vector<int> C[maxm][maxn]; __float128 C_[maxn][maxn];
int n, m;
__float128 tot, f[maxn];
__float128 Ans;
int main()
{
for (int i = 0; i < maxm; i++)
{
C[i][0] = { 1 };
for (int j = 1; j <= i && j < maxn; j++) C[i][j] = C[i - 1][j - 1], add(C[i][j], C[i - 1][j]);
}
for (int i = 0; i < maxn; i++)
{
C_[i][0] = 1;
for (int j = 1; j <= i && j < maxn; j++) C_[i][j] = C_[i - 1][j - 1] + C_[i - 1][j];
}
// cout << C_[50][25] << endl;
// cout << trans(C[50][25]) << endl;
// for (int x : C[50][25]) printf("%9d", x); cerr << endl;
// return 0;
cin >> n >> m;
tot = trans(C[m][n]);
// cout << tot << endl;
for (int i = 1; i <= n; i++)
{
vector<int> now;
for (int j = 0; m - i * j >= n; j++) add(now, C[m - i * j][n]);
f[i] = trans(now) / tot;
// cerr << f[i] << endl;
}
cout << setprecision(12);
for (int k = n; k; k--)
{
for (int i = k; i <= n; i++)
{
Ans += f[i] * C_[i - 1][k - 1] * C_[n][i] * (i - k & 1 ? -1 : 1);
}
cout << (double)Ans << endl;
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 50ms
memory: 40560kb
input:
3 5
output:
1 2.3 4.5
result:
ok 3 numbers
Test #2:
score: 0
Accepted
time: 51ms
memory: 40720kb
input:
5 17
output:
1.13138332256 2.74838396897 5.18309631545 8.85568842922 15
result:
ok 5 numbers
Test #3:
score: 0
Accepted
time: 44ms
memory: 40624kb
input:
50 10000
output:
4.43281643354 12.8365968668 25.3152687339 41.9556112383 62.8480760618 88.0871546758 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.90065489 1181.2...
result:
ok 50 numbers
Test #4:
score: 0
Accepted
time: 58ms
memory: 40580kb
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: 62ms
memory: 40564kb
input:
39 1489
output:
1.52708756282 3.93901256521 7.34033024353 11.763493745 17.236701363 23.7907109205 31.4582877129 40.2742330903 50.2755910473 61.501875303 73.9953246967 87.8011951264 102.968094779 119.548370932 137.598558645 157.179904233 178.358979779 201.20840937 225.807733676 252.244447433 280.615255348 311.027607...
result:
ok 39 numbers
Test #6:
score: 0
Accepted
time: 73ms
memory: 40540kb
input:
47 9871
output:
4.88391758537 14.2093220216 28.0939348059 46.6414309717 69.9602357807 98.1639517434 131.371723046 169.708651073 213.306252663 262.302966594 316.84471482 377.085526074 443.188230726 515.325237406 593.679403751 678.445016001 769.828894992 868.051649614 973.349103166 1085.97392347 1206.19749447 1334.31...
result:
ok 47 numbers
Test #7:
score: 0
Accepted
time: 62ms
memory: 40556kb
input:
9 9999
output:
111.556222555 348.049260394 727.328001799 1273.19006403 2018.95211125 3014.58913972 4343.39280984 6171.94644244 9000
result:
ok 9 numbers