Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define sz(x) (int) x.size()
- #define all(a) a.begin(), a.end()
- const int MAXN = 55;
- long long s[MAXN][MAXN];
- int n, a, b;
- int p[MAXN];
- double dp[MAXN];
- long long cnt[MAXN];
- int loopsNum() {
- vector<bool> used(n, 0);
- int res = 0;
- for (int i = 0; i < n; i++) {
- if (used[i]) continue;
- res++;
- int pos = i;
- while (!used[pos]) {
- used[pos] = true;
- pos = p[pos];
- }
- }
- return res;
- }
- int main() {
- scanf("%d %d %d", &n, &a, &b);
- for (int i = 0; i < n; i++) {
- scanf("%d", &p[i]);
- p[i]--;
- }
- s[0][0] = 1;
- for (int i = 0; i < n; i++) {
- for (int j = 1; j <= n; j++) {
- s[i + 1][j] = 1ll * i * s[i][j] + s[i][j - 1];
- }
- }
- // for (int i = 0; i <= n; i++) {
- // for (int j = 0; j <= i; j++) {
- // cerr << s[i][j] << " ";
- // }
- // cerr << endl;
- // }
- long long total = 1;
- // cerr << "CNT" << endl;
- for (int i = 1; i <= n; i++) {
- cnt[i] = s[n][i];
- total = 1ll * total * i;
- // cerr << cnt[i] << " ";
- }
- // cerr << endl << total << endl;
- // cerr << "LOOPS: " << loopsNum() << endl;
- int loops = loopsNum();
- double ans = 1.0 * a * (n - loops);
- for (int i = n; i >= 1; i--) {
- for (int j = n; j >= 1; j--)
- dp[j] = 0.0;
- for (int j = n; j >= 1; j--) {
- if (j >= i) {
- dp[j] = 1.0 * a * (n - j);
- } else {
- dp[j] = 1.0 * b;
- // cerr << "HERE1 " << dp[j] << endl;
- for (int k = n; k >= i; k--)
- dp[j] += 1.0 * dp[k] * cnt[k] / total;
- // cerr << "HERE2 " << dp[j] << endl;
- long long sum = 0;
- for (int k = i - 1; k >= 1; k--)
- sum += cnt[k];
- // cerr << "HERE3 " << dp[j] << endl;
- dp[j] = 1.0 * dp[j] * total / (total - sum);
- }
- // cerr << dp[j] << " ";
- }
- // cerr << endl;
- ans = min(ans, dp[loops]);
- }
- printf("%.12lf\n", ans);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement