QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#108041 | #4228. Double Sort | zaxwellmen | TL | 4ms | 15548kb | C++20 | 1.1kb | 2023-05-23 14:56:18 | 2023-05-23 14:56:31 |
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;
vector<db> dp[51][10001];
map<pi, db> pre;
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);
cin >> n >> m;
FOR(i, 1, n+1) {
dp[i][i].assign(i,1);
// F0R(j, i) dp[i][i][j] = j+1;
FOR(j, i+1, m+1) {
dp[i][j].assign(i,1);
F0R(k, i+1) {
db prob = choose(i,k)*choose(j-i,i-k) / choose(j,i);
FOR(a, k, i) if (j-i >= i-k) 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];
F0R(i, n) cout << dp[n][m][i] << '\n';
}
詳細信息
Test #1:
score: 100
Accepted
time: 3ms
memory: 15548kb
input:
3 5
output:
1.00000000 2.30000000 4.50000000
result:
ok 3 numbers
Test #2:
score: 0
Accepted
time: 4ms
memory: 15456kb
input:
5 17
output:
1.13138332 2.74838397 5.18309632 8.85568843 15.00000000
result:
ok 5 numbers
Test #3:
score: -100
Time Limit Exceeded
input:
50 10000