QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#108055 | #4228. Double Sort | zaxwellmen | AC ✓ | 611ms | 210824kb | C++20 | 1.2kb | 2023-05-23 15:13:04 | 2023-05-23 15:13:07 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef double db;
typedef pair<int, int> pi;
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define F0R(i, a) FOR(i, 0, a)
#define rsz resize
#define mp make_pair
int n, m;
db dp[51][10001][51];
db fact[10001], ch[10001][51];
// db choose(int n, int k) {
// if (pre.find(mp(n,k)) != pre.end()) return pre[mp(n,k)];
// if (k > n) return 0;
// db ans = 1;
// F0R(i, k) ans *= db(n-i) / db(i+1);
// pre[mp(n,k)] = ans;
// return ans;
// }
int main() {
cin.tie(0) -> sync_with_stdio(0);
F0R(k, 51) FOR(n, k, 10001) {
ch[n][k] = 1;
F0R(i, k) ch[n][k] *= db(n-i) / db(i+1);
}
fill(*dp[0], *dp[51], (db)1);
cin >> n >> m;
FOR(i, 1, n+1) {
FOR(j, i, m+1) {
db den = db(1) / ch[j][i];
FOR(k, max(0, 2*i-j), i+1) {
db prob = ch[i][k] * ch[j-i][i-k] * den;
FOR(a, k, i) dp[i][j][a] += dp[i-k][j-i][a-k] * prob;
}
}
}
cout << fixed << setprecision(8);
FOR(i, 1, n) dp[n][m][i] += dp[n][m][i-1];
// cout << "done" << endl; return 0;
F0R(i, n) cout << dp[n][m][i] << '\n';
}
详细
Test #1:
score: 100
Accepted
time: 44ms
memory: 210820kb
input:
3 5
output:
1.00000000 2.30000000 4.50000000
result:
ok 3 numbers
Test #2:
score: 0
Accepted
time: 48ms
memory: 210764kb
input:
5 17
output:
1.13138332 2.74838397 5.18309632 8.85568843 15.00000000
result:
ok 5 numbers
Test #3:
score: 0
Accepted
time: 611ms
memory: 210760kb
input:
50 10000
output:
4.43281643 12.83659687 25.31526873 41.95561124 62.84807606 88.08715468 117.77163378 152.00489478 190.89524200 234.55626293 283.10722438 336.67350947 395.38710039 459.38711351 528.82039390 603.84217776 684.61683284 771.31868857 864.13296997 963.25685207 1068.90065489 1181.28920327 1300.66338100 1427....
result:
ok 50 numbers
Test #4:
score: 0
Accepted
time: 20ms
memory: 210824kb
input:
40 40
output:
1.00000000 2.00000000 3.00000000 4.00000000 5.00000000 6.00000000 7.00000000 8.00000000 9.00000000 10.00000000 11.00000000 12.00000000 13.00000000 14.00000000 15.00000000 16.00000000 17.00000000 18.00000000 19.00000000 20.00000000 21.00000000 22.00000000 23.00000000 24.00000000 25.00000000 26.000000...
result:
ok 40 numbers
Test #5:
score: 0
Accepted
time: 32ms
memory: 210764kb
input:
39 1489
output:
1.52708756 3.93901257 7.34033024 11.76349375 17.23670136 23.79071092 31.45828771 40.27423309 50.27559105 61.50187530 73.99532470 87.80119513 102.96809478 119.54837093 137.59855864 157.17990423 178.35897978 201.20840937 225.80773368 252.24444743 280.61525535 311.02760710 343.60159349 378.47231670 415...
result:
ok 39 numbers
Test #6:
score: 0
Accepted
time: 497ms
memory: 210760kb
input:
47 9871
output:
4.88391759 14.20932202 28.09393481 46.64143097 69.96023578 98.16395174 131.37172305 169.70865107 213.30625266 262.30296659 316.84471482 377.08552607 443.18823073 515.32523741 593.67940375 678.44501600 769.82889499 868.05164961 973.34910317 1085.97392347 1206.19749447 1334.31207581 1470.63330792 1615...
result:
ok 47 numbers
Test #7:
score: 0
Accepted
time: 37ms
memory: 210712kb
input:
9 9999
output:
111.55622256 348.04926039 727.32800180 1273.19006403 2018.95211125 3014.58913972 4343.39280984 6171.94644244 9000.00000000
result:
ok 9 numbers