Submission #946383

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;
#define PB push_back
#define MP make_pair
#define LL long long
#define int LL
#define FOR(i,a,b) for(int i = (a); i <= (b); i++)
#define RE(i,n) FOR(i,1,n)
#define REP(i,n) FOR(i,0,(int)(n)-1)
#define R(i,n) REP(i,n)
#define VI vector<int>
#define PII pair<int,int>
#define LD long double
#define FI first
#define SE second
#define st FI
#define nd SE
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((int)(x).size())

template<class C> void mini(C& _a4, C _b4) { _a4 = min(_a4, _b4); }
template<class C> void maxi(C& _a4, C _b4) { _a4 = max(_a4, _b4); }

template<class TH> void _dbg(const char *sdbg, TH h){ cerr<<sdbg<<'='<<h<<endl; }
template<class TH, class... TA> void _dbg(const char *sdbg, TH h, TA... a) {
  while(*sdbg!=',')cerr<<*sdbg++;cerr<<'='<<h<<','; _dbg(sdbg+1, a...);
}

template<class T> ostream& operator<<(ostream& os, vector<T> V) {
  os << "["; for (auto& vv : V) os << vv << ","; os << "]";
  return os;
}

#ifdef LOCAL
#define debug(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
#else
#define debug(...) (__VA_ARGS__)
#define cerr if(0)cout
#endif

const int P = 1e9 + 7;
const int MAX = 1e6;
int dp[MAX];
int n;
int sum(int x){
  int res = 0;
  for(;x; x -= (x&-x)){
    res += dp[x];
  }
  return res;
}
void add(int x){
  for(;x <= n; x += (x & -x))
    dp[x] ++;
}

int p[MAX];
int zerd[MAX];
int md[MAX];
int sil[MAX];
int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout << fixed << setprecision(11);
  cerr << fixed << setprecision(6);
  cin >> n;
  sil[0] = 1;
  R(i,n){
    sil[i+1] = sil[i] * (i+1) % P;
    cin >> p[i];
  }
  int zer = 0;
  for(int i = n-1;i>=0;i--){
    zerd[i] = zer;
    if(p[i] == 0){
      zer++;
    }else{
      md[i] = sum(p[i]);
      add(p[i]);
    }
  }
  int res = 0;
  int ss = 0;
  R(i,n){
    int pom = 0;
    if(p[i] != 0){
      pom += md[i] * sil[zer] % P;
      int wolne = p[i] - sum(p[i]);
      pom += wolne * sil[zer-1] % P * zerd[i] % P;
      res += ss * (zer - wolne) % P * sil[zer-1] % P;
    }else{
      ss += sil[n-i-1];
      ss %= P;
      pom = sil[zer] * zerd[i]% P * ((P+1) / 2) % P; ;
    }
    debug(pom);
    res += (pom % P * sil[n-i-1]) % P; 
    debug(res);
  }
  debug(res);
  res += sil[zer]; // indeksowanie ??
  cout << res % P << "\n";
}

Submission Info

Judge Result