Submission #946662

---

Source Code Expand

#include <bits/stdc++.h>

/* -------------------------------- Template -------------------------------- */

#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define ALL(x) (x).begin(),(x).end()

using namespace std;

using ll = long long;
using ld = long double;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }

template<typename T> T inf() { assert(false); }
template<> constexpr int inf<int>() { return 1e9; }
template<> constexpr ll inf<ll>() { return 1e18; }
template<> constexpr ld inf<ld>() { return 1e30; }

struct yes_no : numpunct<char> {
  string_type do_truename()  const { return "Yes"; }
  string_type do_falsename() const { return "No"; }
};

/* -------------------------------- Library -------------------------------- */

const int mod = 1000000007;

struct Mod {
  int n;
  Mod () : n(0) {;}
  Mod (int m) : n(m) {
    if (n >= mod) n %= mod;
    else if (n < 0) n = (n % mod + mod) % mod;
  }
};

bool operator==(Mod a, Mod b) { return a.n == b.n; }
Mod operator+=(Mod &a, Mod b) { a.n += b.n; if (a.n >= mod) a.n -= mod; return a; }
Mod operator-=(Mod &a, Mod b) { a.n -= b.n; if (a.n < 0) a.n += mod; return a; }
Mod operator*=(Mod &a, Mod b) { a.n = ((long long)a.n * b.n) % mod; return a; }
Mod operator+(Mod a, Mod b) { return a += b; }
Mod operator-(Mod a, Mod b) { return a -= b; }
Mod operator*(Mod a, Mod b) { return a *= b; }
Mod operator^(Mod a, int n) {
  if (n == 0) return Mod(1);
  Mod res = (a * a) ^ (n / 2);
  if (n % 2) res = res * a;
  return res;
}

ll inv(ll a, ll p) {
  return (a == 1 ? 1 : (1 - p * inv(p%a, a)) / a + p);
}
Mod operator/(Mod a, Mod b) { return a * Mod(inv(b.n, mod)); }

#define MAX_N 1024000

Mod fact[MAX_N], factinv[MAX_N];
void init() {
  fact[0] = Mod(1); factinv[0] = 1;
  REP(i,MAX_N-1) {
    fact[i+1] = fact[i] * Mod(i+1);
    factinv[i+1] = factinv[i] / Mod(i+1);
  }
}
Mod comb(int a, int b) {
  return fact[a] * factinv[b] * factinv[a-b];
}

struct Data {
  int num;
  Data() : num(0) {;}
  Data(int n) : num(n) {;}
};

inline Data Merge(Data left, Data right) {
  return Data(left.num + right.num);
}

struct BIT {
  static const int len = 1 << 19;
  vector<Data> data;
  BIT() : data(len, 0) {}
  void update(int i, Data value) {
    for (; i < len; i |= i+1) data[i] = Merge(data[i], value);
  }
  Data query(int i) {
    Data s = 0;
    for (; i >= 0; i = (i&(i+1))-1) s = Merge(s, data[i]);
    return s;
  }
};

/* ---------------------------------- Main ---------------------------------- */

int pos[512000];
int val[512000];
int pos_sum[512000];
int val_sum[512000];

int main() {
  locale loc(locale(), new yes_no);
  cout << boolalpha;
  cout.imbue(loc);
  init();

  int N;
  cin >> N;
  vector<int> P(N);
  for (int &i: P) { cin >> i; --i; }
  REP(i,N) {
    if (P[i] != -1) {
      pos[i] = 1;
      val[P[i]] = 1;
    }
  }
  REP(i,N) {
    pos_sum[i+1] = pos_sum[i] + pos[i];
    val_sum[i+1] = val_sum[i] + val[i];
  }
  Mod res = 0;
  const int cnt = N - (pos_sum[N] - pos_sum[0]);
  Mod base = fact[cnt];
  const Mod half = inv(2LL, mod);
  Mod cntinv = cnt == 0 ? 0 : inv(ll(cnt), mod);
  int c = 0;
  Mod prob = 0;
  for (int i = N-1; i >= 0; --i) {
    if (P[i] != -1) {
      prob += Mod((N - P[i]) - (val_sum[N] - val_sum[P[i]])) * cntinv;
    }
    else {
      res += prob * fact[c];
      prob += half;
    }
    ++c;
  }
  // cout << (base * res).n << endl;

  BIT bit;
  c = 0;
  int d = 0;
  for (int i = N-1; i >= 0; --i) {
    if (P[i] != -1) {
      //      res += (Mod(d) * Mod((N - P[i]) - (val_sum[N] - val_sum[P[i]])) * cntinv
      res += (Mod(d) * Mod(P[i] - val_sum[P[i]]) * cntinv
              + Mod(bit.query(P[i]).num))
        * fact[c];
      bit.update(P[i], 1);
    }
    else ++d;
    ++c;
  }
  //  cout << (base * res).n << endl;
  cout << (base * res + fact[cnt]).n << endl;
  return 0;
}

Submission Info

Judge Result