Advertisement
Guest User

Untitled

a guest
Apr 7th, 2020
361
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.24 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define sz(x) (int) x.size()
  6. #define all(a) a.begin(), a.end()
  7.  
  8. const int MAXN = 55;
  9.  
  10. long long s[MAXN][MAXN];
  11.  
  12. int n, a, b;
  13. int p[MAXN];
  14. double dp[MAXN];
  15. long long cnt[MAXN];
  16.  
  17. int loopsNum() {
  18.     vector<bool> used(n, 0);
  19.     int res = 0;
  20.     for (int i = 0; i < n; i++) {
  21.         if (used[i]) continue;
  22.         res++;
  23.         int pos = i;
  24.         while (!used[pos]) {
  25.             used[pos] = true;
  26.             pos = p[pos];
  27.         }
  28.     }
  29.     return res;
  30. }
  31.  
  32. int main() {
  33.  
  34.     scanf("%d %d %d", &n, &a, &b);
  35.     for (int i = 0; i < n; i++) {
  36.         scanf("%d", &p[i]);
  37.         p[i]--;
  38.     }
  39.  
  40.     s[0][0] = 1;
  41.     for (int i = 0; i < n; i++) {
  42.         for (int j = 1; j <= n; j++) {
  43.             s[i + 1][j] = 1ll * i * s[i][j] + s[i][j - 1];
  44.         }
  45.     }
  46.     // for (int i = 0; i <= n; i++) {
  47.     //     for (int j = 0; j <= i; j++) {
  48.     //         cerr << s[i][j] << " ";
  49.     //     }
  50.     //     cerr << endl;
  51.     // }
  52.  
  53.     long long total = 1;
  54.     // cerr << "CNT" << endl;
  55.     for (int i = 1; i <= n; i++) {
  56.         cnt[i] = s[n][i];
  57.         total = 1ll * total * i;
  58.         // cerr << cnt[i] << " ";
  59.     }
  60.     // cerr << endl << total << endl;
  61.  
  62.     // cerr << "LOOPS: " << loopsNum() << endl;
  63.     int loops = loopsNum();
  64.  
  65.     double ans = 1.0 * a * (n - loops);
  66.  
  67.     for (int i = n; i >= 1; i--) {
  68.         for (int j = n; j >= 1; j--)
  69.             dp[j] = 0.0;
  70.         for (int j = n; j >= 1; j--) {
  71.             if (j >= i) {
  72.                 dp[j] = 1.0 * a * (n - j);
  73.             } else {
  74.                 dp[j] = 1.0 * b;
  75.                 // cerr << "HERE1 " << dp[j] << endl;
  76.                 for (int k = n; k >= i; k--)
  77.                     dp[j] += 1.0 * dp[k] * cnt[k] / total;
  78.                 // cerr << "HERE2 " << dp[j] << endl;
  79.                 long long sum = 0;
  80.                 for (int k = i - 1; k >= 1; k--)
  81.                     sum += cnt[k];
  82.                 // cerr << "HERE3 " << dp[j] << endl;
  83.                 dp[j] = 1.0 * dp[j] * total / (total - sum);
  84.             }
  85.             // cerr << dp[j] << " ";
  86.         }
  87.         // cerr << endl;
  88.         ans = min(ans, dp[loops]);
  89.     }
  90.  
  91.     printf("%.12lf\n", ans);
  92.  
  93.     return 0;
  94. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement