fork download 
  1. #include <algorithm>
  2. #include <iostream>
  3. #include <vector>
  4. using namespace std;
  5.  
  6. #define all(x) (x).begin(), (x).end()
  7. typedef long long ll;
  8. int readInt() { int x; return cin >> x, x; }
  9.  
  10. int n, k;
  11. vector<ll> BIT;
  12.  
  13. void update(int p) {
  14.     for (; p <= n; p += p & -p)
  15.         BIT[p]++;
  16. }
  17.  
  18. void reverse(int p) {
  19.     for (; p <= n; p += p & -p)
  20.         BIT[p]--;
  21. }
  22.  
  23. ll getValue(int p) {
  24.     ll res = 0;
  25.     for (p--; p > 0; p -= p & -p)
  26.         res += BIT[p];
  27.  
  28.     return res;
  29. }
  30.  
  31. int query()
  32. {
  33.     cin >> n;
  34.     vector<int> perm(n + 1);
  35.     for (int i = 1; i <= n; ++i)
  36.         perm[i] = i;
  37.  
  38.     vector<ll> cal(n + 1, 0);
  39.     BIT.assign(n + 1, 0);
  40.     for (int i = 1; i <= n; ++i)
  41.     {
  42.         cal[i] = cal[i - 1] + 1LL * perm[i] * getValue(perm[i]);
  43.         update(perm[i]);
  44.     }
  45.  
  46.     ll res = cal[n];
  47.     vector<int> n_perm(perm);
  48.     while (true) {
  49.         if (!next_permutation(1 + all(n_perm))) break;
  50.         int p = 1;
  51.         for (int l = 1, r = n; l <= r; )
  52.         {
  53.             int m = (l + r)/ 2;
  54.             if (perm[m] == n_perm[m] && perm[m - 1] == n_perm[m - 1])
  55.             {
  56.                 p = m;
  57.                 l = m + 1;
  58.             }
  59.             else 
  60.                 r = m - 1;
  61.         }
  62.  
  63.         for (int i = p; i <= n; ++i)
  64.             reverse(perm[i]);
  65.  
  66.         for (int i = p; i <= n; ++i)
  67.         {
  68.             cal[i] = cal[i - 1] + 1LL * n_perm[i] * getValue(n_perm[i]);
  69.             update(n_perm[i]);
  70.         }
  71.         res += cal[n];
  72.         next_permutation(1 + all(perm));
  73.     }
  74.     cout << res << '\n';
  75.     return 0;
  76. }
  77.  
  78. int main()
  79. {
  80.     for (int q = readInt(); q--; )
  81.     {
  82.         if (query());
  83.  
  84.  
  85.  
  86.     }
  87. }
Success #stdin #stdout 0.18s 4200KB
comments (?)
stdin 
10
1 2 3 4 5 6 7 8 9 10
stdout 
0
2
24
240
2400
25200
282240
3386880
43545600
598752000
https://ideone.com/LEqnvq
language:
C++14 (gcc 8.3)
created:
3 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!