Advertisement
Guest User

Untitled

a guest
Apr 7th, 2020
155
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.85 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define x first
  3. #define y second
  4. using namespace std;
  5. typedef long long ll;
  6. const int MAXN = 100500;
  7. const int N = 25;
  8. ll dp[N][N];
  9. ll n, a, b;
  10. int p[N];
  11. ll C[N][N];
  12. ll fact[N];
  13. bool used[N];
  14. double ans[N];
  15.  
  16. int main()
  17. {                                                    
  18.     ios_base::sync_with_stdio(0);
  19.     cin >> n >> a >> b;
  20.     for (int i = 0; i < n; i++)
  21.     {
  22.         cin >> p[i];
  23.         p[i]--;
  24.     }
  25.     fact[0] = 1;
  26.     C[0][0] = 1;
  27.     for (int i = 0; i < N - 1; i++)
  28.     {
  29.         fact[i + 1] = (ll)(i + 1) * fact[i];
  30.         for (int j = 0; j < N - 1; j++)
  31.         {
  32.             C[i + 1][j + 1] += C[i][j];
  33.             C[i + 1][j] += C[i][j];
  34.         }
  35.     }
  36.     for (int i = 1; i <= n; i++)
  37.     {
  38.         dp[i][1] = fact[i - 1];
  39.     }
  40.  
  41.     for (int sz = 2; sz <= n; sz++)
  42.     {
  43.         for (int i = 1; i <= n; i++)
  44.         {
  45.             for (int k = 1; k <= i; k++)
  46.             {
  47.                 dp[i][sz] += dp[i - k][sz - 1] * fact[k - 1] * C[i - 1][k - 1];
  48.             }
  49.         }
  50.     }
  51.  
  52.     int cur_cycles = 0;
  53.     for (int i = 0; i < n; i++)
  54.     {
  55.         if (!used[i])
  56.         {
  57.             cur_cycles++;
  58.             int j = i;
  59.             while (!used[j])
  60.             {
  61.                 used[j] = true;
  62.                 j = p[j];
  63.             }
  64.         }
  65.     }
  66.  
  67.     double best_ans;
  68.     bool is_ba_found = false;
  69.     for (int strat = 1; strat <= n; strat++)
  70.     {
  71.         double lower_res = 0;
  72.         double q = 0;
  73.         for (int c = n; c >= 1; c--)
  74.         {
  75.             if (c >= strat)
  76.             {
  77.                 ans[c] = (double)(n - c) * a;
  78.                 lower_res += ans[c] * dp[n][c];
  79.                
  80.             }
  81.             else
  82.             {
  83.                 ans[c] = b / q +
  84.             }
  85.         }
  86.         if (best_ans)
  87.     }
  88.    
  89.     return 0;
  90. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement