Submission #945301

---

Source Code Expand

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <cmath>
#include <map>
using namespace std;
#define MOD 1000000007
#define ADD(X,Y) ((X) = ((X) + (Y)%MOD) % MOD)
typedef long long i64; typedef vector<int> ivec; typedef vector<string> svec;

i64 modpow(i64 a, int p = MOD - 2)
{
	if (p == 0) return 1;
	i64 ret = modpow(a, p / 2);
	ret = ret * ret % MOD;
	if (p % 2 == 1) ret = ret * a % MOD;
	return ret;
}

struct segtree
{
	static const int DEPTH = 19;
	static const int N = 1 << DEPTH;

	int val[2 * N];

	void init()
	{
		for (int i = 0; i < 2 * N; ++i) val[i] = 0;
	}

	void incl(int p, int v)
	{
		p += N;
		while (p) {
			val[p] += v;
			p >>= 1;
		}
	}

	int query(int L, int R)
	{
		L += N; R += N;
		int ret = 0;
		while (L < R) {
			if (L & 1) ret += val[L++];
			if (R & 1) ret += val[--R];
			L >>= 1; R >>= 1;
		}
		return ret;
	}
};
int N, P[505050];
vector<int> uus;
bool used[505050];
segtree seg;
i64 invs[505050];

int main()
{
	scanf("%d", &N);
	for (int i = 0; i < N; ++i) {
		scanf("%d", P + i);
		--P[i];
	}
	invs[0] = 0;
	for (int i = 1; i <= N; ++i) invs[i] = modpow(i);

	i64 mult = 1;
	int uu = 0;

	for (int i = 0; i < N; ++i) {
		if (P[i] >= 0) used[P[i]] = true;
	}
	for (int i = 0; i < N; ++i) if (!used[i]) uus.push_back(i);

	seg.init();

	i64 ret = 0;
	i64 ap = 0;
	i64 waf = uus.size() * (uus.size() - 1) / 2 % MOD;
	waf = waf * invs[uus.size()] % MOD;
	if (uus.size() > 0) waf = waf * invs[uus.size() - 1] % MOD;

	i64 fuee = 1;
	int pohe = 0;
	for (int i = 0; i < N; ++i) {
		if (P[i] == -1) {
			++pohe;
			fuee = fuee * pohe % MOD;
		}
	}

	i64 m2 = 1;
	for (int i = N - 1; i >= 0; --i) {
		if (P[i] == -1) {
		//	ADD(ret, ap);
			ADD(ret, (waf * uu % MOD + ap * invs[uus.size()]) % MOD * m2 % MOD * fuee % MOD);
///			printf("%lld\n", (waf * uu + ap * invs[uus.size()]) % MOD * m2 % MOD * fuee % MOD);
//			printf("%lld %lld\n", uu, ap);
			++uu;
			mult = mult * uu % MOD;
		} else {
			int lt = lower_bound(uus.begin(), uus.end(), P[i]) - uus.begin();
			int gt = uus.size() - lt;
	//		int gt = (uus.size() - (lower_bound(uus.begin(), uus.end(), P[i]) - uus.begin()));
//			int lt = uus.size() - lt;
//			printf("%d %d\n", lt, gt);
			ADD(ap, gt);
			ADD(ret, (seg.query(0, P[i]) + lt * invs[uus.size()] % MOD * uu) % MOD * m2 % MOD * fuee);
			seg.incl(P[i], 1);
		}
		m2 *= N - i;
		m2 %= MOD;
	}
//	printf("%lld\n", mult);

	ADD(ret, mult);
//	ADD(ret, 1);
	//ret = ret * mult % MOD;

	printf("%lld\n", ret);

	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:68:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
                 ^
./Main.cpp:70:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", P + i);
                     ^

Judge Result