Advertisement
pasholnahuy

Untitled

Jan 13th, 2024
82
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.71 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. int main() {
  33. int64 n;
  34. cin >> n;
  35. vector<int64> perm(n);
  36. for (int64 i = 0; i < n; ++i) {
  37. cin >> perm[i];
  38. }
  39. int64 cnt = 0;
  40. int64 start_cnt = inv_cnt(perm);
  41. vector<vector<int64>> pr(n, vector<int64>(n, 0));
  42. for (int i = 0; i < n; ++i) {
  43. pr[i][i] = 0;
  44. for (int j = i + 1; j < n; ++j) {
  45. if (perm[i] < perm[j]) {
  46. pr[i][j] = pr[i][j - 1] + 1;
  47. } else {
  48. pr[i][j] = pr[i][j - 1] - 1;
  49. }
  50. }
  51. for (int j = i - 1; j >= 0; --j) {
  52. if (perm[i] > perm[j]) {
  53. pr[i][j] = pr[i][j + 1] + 1;
  54. } else {
  55. pr[i][j] = pr[i][j + 1] - 1;
  56. }
  57. }
  58. }
  59. for (int i = 0; i < n; ++i) {
  60. for (int j = i + 1; j < n; ++j) {
  61. cnt += start_cnt + pr[i][j] + pr[j][i];
  62. if (perm[i] > perm[j]){
  63. ++cnt;
  64. } else{
  65. --cnt;
  66. }
  67. }
  68. }
  69.  
  70. int64 all = n * (n - 1) / 2;
  71. int64 g = gcd(cnt, all);
  72. cout << cnt / g << '/' << all /
  73. g;
  74. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement