Submission #945667

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
int modulo(1e9 + 7);
const int N(555555);
int a[N], cnt[N], le[N], bt[N], fac[N];
bool vst[N];
int n;
int getSum(int x) {
	int res(0);
	for(int i(x); i; i -= i & -i)
		res += bt[i];
	return res;
}
void inc(int x) {
	for(int i(x); i <= n; i += i & -i)
		bt[i] += 1;
}
int main() {
	cin >> n;
	fac[0] = 1;
	for(int i(1); i <= n; i++) {
		fac[i] = 1ll * i * fac[i - 1] % modulo;
	}
	for(int i(1); i <= n; i++) {
		cin >> a[i];
		cnt[i] = cnt[i - 1];
		if(a[i] == 0) {
			cnt[i]++;
		}else {
			vst[a[i]] = true;
		}
	}
	int sum(0);
	for(int i(1); i <= n; i++) {
		if(!vst[i]) {
			le[i] = 1;
			sum = (sum + i) % modulo;
		}
	}
	for(int i(1); i <= n; i++) {
		le[i] += le[i - 1];
	}
	int ans(0), cur(0);
	for(int i(1); i <= n; i++) {
		if(a[i]) {
			int tmp(0);
			tmp = (tmp + 1ll * (a[i] - 1) * fac[cnt[n]]) % modulo;
			int nu(getSum(a[i]));
			tmp = (tmp - 1ll * fac[cnt[n]] * nu % modulo + modulo) % modulo;
			//k = cnt[i], l = cnt[n] - k, a = le[a[i]]
			if(cnt[i]) {
				tmp = (tmp - 1ll * le[a[i]] * cnt[i] % modulo * fac[cnt[n] - 1] % modulo + modulo) % modulo;
			}
			//printf("tmp[%d] = %d\n", i, tmp);
			ans = (ans + 1ll * fac[n - i] * tmp) % modulo;
			inc(a[i]);
			cur = (cur + (cnt[n] - le[a[i]])) % modulo;
		}else {
			//k = cnt[i], m = cnt[n]
			int tmp(0);
			tmp = (tmp + 1ll * (sum - cnt[n] + modulo) * fac[cnt[n] - 1]) % modulo;

			tmp = (tmp - 1ll * cnt[n] * (cnt[n] - 1) / 2 % modulo * (cnt[i] - 1) % modulo * fac[cnt[n] - 2] % modulo + modulo) % modulo;
			tmp = (tmp - 1ll * cur * fac[cnt[n] - 1] % modulo + modulo) % modulo;
			ans = (ans + 1ll * fac[n - i] * tmp) % modulo;
		}

	}
	cout << (ans + fac[cnt[n]]) % modulo << endl;
}

Submission Info

Judge Result