Run ID | 作者 | 问题 | 语言 | 测评结果 | 分数 | 时间 | 内存 | 代码长度 | 提交时间 |
---|---|---|---|---|---|---|---|---|---|
52876 | _ | 敏捷排列 | C++ | 运行超时 | 0 | 1000 MS | 256 KB | 1245 | 2022-07-20 12:05:51 |
#include <bits/stdc++.h> using namespace std; const int MXN = 22; const int lim = 2000000; int bgn[MXN], N, A, B, cnt; long long eff[MXN][MXN]; bool vis[MXN]; long double ans, fac(1.0); int main() { // freopen("permutation.in", "r", stdin); // freopen("permutation.out", "w", stdout); cin >> N >> A >> B; for (int i(0); i != N; ++i) cin >> bgn[i], --bgn[i]; eff[0][0] = 1; for (int i(1); i <= N; ++i) { for (int j(1); j <= i; ++j) { eff[i][j] = eff[i - 1][j - 1] + (i - 1) * 1LL * eff[i - 1][j]; } } for (int i(0); i != N; ++i) { while (i != N && vis[i]) ++i; if (i == N) break; ++cnt; for (int j(i); !vis[j]; j = bgn[j]) { vis[j] = true; } } ans = (N - cnt) * 1.0 * A; for (int i(1); i <= N; ++i) fac *= i; for (int i(cnt + 1); i <= N; ++i) { long double sum(0); for (int j(i); j <= N; ++j) sum += eff[N][j]; long double tans(0); for (int j(1); j <= lim; ++j) tans += j * pow(1 - sum / fac, j - 1) * sum / fac; tans = tans * B; for (int j(i); j != N; ++j) tans += eff[N][j] / sum * A * j; // cout << i << ':' << sum << ',' << fac << ',' << tans << endl; ans = min(ans, tans); } cout << setprecision(10) << fixed << ans << endl; return 0; }