Advertisement
veschii_nevstrui

Untitled

Nov 2nd, 2021
491
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.96 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. long long mod = 1e9 + 7;
  6.  
  7. int f(int i) {
  8.     return i & (i + 1);
  9. }
  10.  
  11. int g(int i) {
  12.     return i | (i + 1);
  13. }
  14.  
  15. struct fenwick {
  16.     vector <int> s;
  17.     fenwick(int n) {
  18.         s.resize(n + 1, 0);
  19.     }
  20.     int get(int r) {
  21.         int sum = 0;
  22.         for (int i = r; i >= 0; i = f(i) - 1) {
  23.             sum += s[i];
  24.         }
  25.         return sum;
  26.     }
  27.  
  28.     void up(int r, int q) {
  29.         for (int i = r; i < s.size(); i = g(i)) {
  30.             s[i] += q;
  31.         }
  32.     }
  33. };
  34.  
  35. int main()
  36. {
  37.     ios_base::sync_with_stdio(0);
  38.     cin.tie(0);
  39.     cout.tie(0);
  40.     cout.setf(ios::fixed);
  41.     cout.precision(10);
  42.  
  43.     int n;
  44.     cin >> n;
  45.  
  46.     vector <long long> fact(n + 1, 1);
  47.     for (long long i = 1; i <= n; ++i) {
  48.         fact[i] = (fact[i - 1] * i) % mod;
  49.     }
  50.  
  51.     fenwick t(n);
  52.  
  53.     long long ans = 0;
  54.  
  55.     for (int i = 0; i < n; ++i) {
  56.         int a;
  57.         cin >> a;
  58.         ans += fact[n - i - 1] * (a - t.get(a - 1) - 1);
  59.         ans %= mod;
  60.         t.up(a, 1);
  61.     }
  62.  
  63.     cout << ans + 1 << endl;
  64.     return 0;
  65. }
  66.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement