Submission #945759

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;

#define get dlafkjsdlfajks

const int M = 500100;
const int mod = 1e9 + 7;

int add(int x, int y) {
  x += y;
  if (x >= mod)
    x -= mod;
  return x;
}

int mul(ll x, ll y) {
  return x * y % mod;
}

int fact[M];

void pre() {
  fact[0] = 1;
  for (int i = 1; i < M; ++i) {
    fact[i] = mul(i, fact[i - 1]);
  }
}

int bin(int x, int to) {
  int y = 1;
  while (to) {
    if (to & 1)
      y = mul(x, y);
    x = mul(x, x);
    to >>= 1;
  }
  return y;
}

int inv(int x) {
  //assert(x != 0);
  return bin(x, mod - 2);
}

int f[M];
int n, p[M], sm[M];
bool u[M];

void addf(int at, int what) {
  for (int i = at; i < M; i |= (i + 1))
    f[i] += what;
}

int get(int r) {
  int ans = 0;
  for (int i = r - 1; i >= 0; i = (i & (i + 1)) - 1)
    ans += f[i];
  return ans;
}

int get(int l, int r) {
  return get(r) - get(l);
}

void read() {
  cin >> n;
  for (int i = 0; i < n; ++i) {
    cin >> p[i];
    --p[i];

    if (p[i] != -1) {
      u[p[i]] = true;
    }
  }
}

void kill() {
  int cnt = 0;
  for (int i = 0; i < n; ++i)
    if (!u[i]) {
      sm[i] = 1;
      ++cnt;
    }

  for (int i = 1; i <= n; ++i)
    sm[i] += sm[i - 1];

  int ans = 0;
  int ma = 0;
  int i2 = (mod + 1) / 2;
  int sum = 0;

  for (int i = n - 1; i >= 0; --i) {
    int bon = 0;

    if (p[i] == -1) {
      bon = add(bon, mul(ma, i2));
      bon = add(bon, mul(sum, inv(cnt)));
      ++ma;
    } else {
      bon = add(bon, mul(mul(ma, sm[p[i]]), inv(cnt)));
      bon = add(bon, get(-1, p[i]));
      addf(p[i], 1);
      sum = add(sum, cnt - sm[p[i]]);
    }

    int rest = n - 1 - i;
    ans = add(ans, mul(bon, fact[rest]));
  }

  ans = add(ans, 1);
  ans = mul(ans, fact[cnt]);
  cout << ans << endl;
}

int main() {
  cout.precision(20);
  cout << fixed;
  ios_base::sync_with_stdio(false);
  pre();
  read();
  kill();
}

Submission Info

Judge Result