Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <cinttypes>
- #include <unordered_set>
- using namespace std;
- using int64 = int64_t;
- int64 gcd(int64 a, int64 b) {
- while (a != 0 && b != 0) {
- if (a < b) {
- swap(a, b);
- }
- a = a % b;
- }
- return b;
- }
- int64 inv_cnt(vector<int64> &perm) {
- int64 ans = 0;
- for (int i = 0; i < perm.size(); ++i) {
- for (int j = i + 1; j < perm.size(); ++j) {
- if (perm[i] > perm[j]) {
- ++ans;
- }
- }
- }
- return ans;
- }
- int64 inv_cnt_ind(vector<int64> &perm, int64 ind) {
- int64 ans = 0;
- for (int i = 0; i < perm.size(); ++i) {
- if ((perm[i] > perm[ind] && i < ind) || (perm[i] < perm[ind] && i > ind)) {
- ++ans;
- }
- }
- return ans;
- }
- int main() {
- int64 n;
- cin >> n;
- vector<int64> perm(n);
- for (int64 i = 0; i < n; ++i) {
- cin >> perm[i];
- }
- int64 cnt = 0;
- int64 start_cnt = inv_cnt(perm);
- vector<vector<int64>> pr(n, vector<int64>(n, 0));
- for (int i = 0; i < n; ++i) {
- pr[i][i] = inv_cnt_ind(perm, i);
- for (int j = i + 1; j < n; ++j) {
- if (perm[i] < perm[j]) {
- pr[i][j] = pr[i][j - 1] + 1;
- } else {
- pr[i][j] = pr[i][j - 1];
- }
- }
- for (int j = i - 1; j >= 0; --j) {
- if (perm[i] > perm[j]) {
- pr[i][j] = pr[i][j + 1] + 1;
- } else {
- pr[i][j] = pr[i][j + 1];
- }
- }
- }
- for (int i = 0; i < n; ++i) {
- for (int j = i + 1; j < n; ++j) {
- cnt += start_cnt + pr[i][j] + pr[j][i] - pr[i][i] - pr[j][j];
- if (perm[i] > perm[j]) {
- cnt -= 2;
- }
- }
- }
- int64 all = n * (n - 1) / 2;
- int64 g = gcd(cnt, all);
- cout << cnt / g << '/' << all /
- g;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement