Advertisement
pasholnahuy

Untitled

Jan 13th, 2024 (edited)
1,192
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.96 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <cinttypes>
  4. #include <unordered_set>
  5.  
  6. using namespace std;
  7. using int64 = int64_t;
  8.  
  9. int64 gcd(int64 a, int64 b) {
  10.     while (a != 0 && b != 0) {
  11.         if (a < b) {
  12.             swap(a, b);
  13.         }
  14.         a = a % b;
  15.     }
  16.     return b;
  17. }
  18.  
  19.  
  20. int64 inv_cnt(vector<int64> &perm) {
  21.     int64 ans = 0;
  22.     for (int i = 0; i < perm.size(); ++i) {
  23.         for (int j = i + 1; j < perm.size(); ++j) {
  24.             if (perm[i] > perm[j]) {
  25.                 ++ans;
  26.             }
  27.         }
  28.     }
  29.     return ans;
  30. }
  31.  
  32. int64 inv_cnt_ind(vector<int64> &perm, int64 ind) {
  33.     int64 ans = 0;
  34.     for (int i = 0; i < perm.size(); ++i) {
  35.         if ((perm[i] > perm[ind] && i < ind) || (perm[i] < perm[ind] && i > ind)) {
  36.             ++ans;
  37.         }
  38.     }
  39.     return ans;
  40. }
  41.  
  42. int main() {
  43.     int64 n;
  44.     cin >> n;
  45.     vector<int64> perm(n);
  46.     for (int64 i = 0; i < n; ++i) {
  47.         cin >> perm[i];
  48.     }
  49.     int64 cnt = 0;
  50.     int64 start_cnt = inv_cnt(perm);
  51.     vector<vector<int64>> pr(n, vector<int64>(n, 0));
  52.     for (int i = 0; i < n; ++i) {
  53.         pr[i][i] = inv_cnt_ind(perm, i);
  54.         for (int j = i + 1; j < n; ++j) {
  55.             if (perm[i] < perm[j]) {
  56.                 pr[i][j] = pr[i][j - 1] + 1;
  57.             } else {
  58.                 pr[i][j] = pr[i][j - 1];
  59.             }
  60.         }
  61.         for (int j = i - 1; j >= 0; --j) {
  62.             if (perm[i] > perm[j]) {
  63.                 pr[i][j] = pr[i][j + 1] + 1;
  64.             } else {
  65.                 pr[i][j] = pr[i][j + 1];
  66.             }
  67.         }
  68.     }
  69.     for (int i = 0; i < n; ++i) {
  70.         for (int j = i + 1; j < n; ++j) {
  71.             cnt += start_cnt + pr[i][j] + pr[j][i] - pr[i][i] - pr[j][j];
  72.             if (perm[i] > perm[j]) {
  73.                 cnt -= 2;
  74.             }
  75.         }
  76.     }
  77.  
  78.     int64 all = n * (n - 1) / 2;
  79.     int64 g = gcd(cnt, all);
  80.     cout << cnt / g << '/' << all /
  81.                               g;
  82. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement