提出 #26190647

---

ソースコード 拡げる

#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b) for(int i = (a); i <= (b); ++ i)
#define per(i, a, b) for(int i = (a); i >= (b); -- i)
#define rep0(i, a) for(int i = 0; i < (a); ++ i)

#define MP make_pair
#define fi first
#define se second

#define pb push_back
#define SIZ(x) (int)(x).size()
#define All(x) (x).begin(),(x).end()

#define Fill(a, b) memset(a, b, sizeof(a))

template <typename T1, typename T2> void CMax(T1 &x, T2 y) {if (y > x) x = y;}
template <typename T1, typename T2> void CMin(T1 &x, T2 y) {if (y < x) x = y;}
template <typename T> void read(T &x) {
	x = 0; int op = 1; char c = getchar();
	while (!isdigit(c)) {
		if (c == '-') op = -1;
		c = getchar();
	}
	while (isdigit(c)) {
		x = (x << 1) + (x << 3) + (c ^ 48);
		c = getchar();
	}
	x *= op;
}

typedef long long LL;
typedef unsigned int ui;
typedef unsigned long long ull;

typedef pair <int, int> pii;
typedef pair <long long, int> pli;
typedef pair <long long, long long> pll;

inline void swap(int &x, int &y) {x ^= y ^= x ^= y;}
inline int min(int x, int y) {return x < y ? x : y;}
inline int max(int x, int y) {return x > y ? x : y;}

const int Mod = 1000000007;
const int inv2 = 500000004;
int Pls(int x, int y) {x += y; return x >= Mod ? x - Mod : x;}
int Sub(int x, int y) {x -= y; return x < 0 ? x + Mod : x;}
int power(int x, int p) {
	int ret = 1;
	while (p) {
		if (p & 1) ret = 1ll * ret * x % Mod;
		x = 1ll * x * x % Mod; p >>= 1;
	} return ret;
}
int Inv(int x) {return power(x, Mod - 2);}

const int MN = 200000 + 10;
const int MS = MN << 2;

int N;
pii A[MN];

int sum[MS], mul[MS], cnt[MS];
#define mid ((l + r) >> 1)
#define ls (x << 1)
#define rs (x << 1 | 1)
void pushup(int x) {
	sum[x] = Pls(sum[ls], sum[rs]);
	cnt[x] = cnt[ls] + cnt[rs];
}
void pushmul(int x, int v) {
	if (!x) return;
	sum[x] = 1ll * sum[x] * v % Mod;
	mul[x] = 1ll * mul[x] * v % Mod;
}
void pushdown(int x) {
	if (mul[x] == 1) return;
	pushmul(ls, mul[x]); pushmul(rs, mul[x]);
	mul[x] = 1;
}
void Build(int x = 1, int l = 1, int r = N) {
	mul[x] = 1; if (l == r) return;
	Build(ls, l, mid); Build(rs, mid + 1, r);
}
void Mdf(int pos, int v, int x = 1, int l = 1, int r = N) {
	if (l == r) {sum[x] = v; cnt[x] = 1; return;}
	pushdown(x);
	if (pos <= mid) Mdf(pos, v, ls, l, mid);
	else Mdf(pos, v, rs, mid + 1, r);
	pushup(x);
}
void Mdf2(int v) {pushmul(1, v);}
int Qsum(int L, int R, int x = 1, int l = 1, int r = N) {
	if (L <= l && r <= R) return sum[x];
	pushdown(x); int ret = 0;
	if (L <= mid) ret = Pls(ret, Qsum(L, R, ls, l, mid));
	if (R > mid) ret = Pls(ret, Qsum(L, R, rs, mid + 1, r));
	return ret;
}
int Qcnt(int L, int R, int x = 1, int l = 1, int r = N) {
	if (L <= l && r <= R) return cnt[x];
	int ret = 0;
	if (L <= mid) ret += Qcnt(L, R, ls, l, mid);
	if (R > mid) ret += Qcnt(L, R, rs, mid + 1, r);
	return ret;
}
#undef mid
#undef ls
#undef rs

int ans, tot = 1;

int main() {
	read(N);
	rep(i, 1, N) read(A[i].fi), A[i].se = i;
	sort(A + 1, A + N + 1);
	Build();
	for (int i = 1; i <= N; ++ i) {
		int inv = Inv(A[i].fi - i + 1); tot = 1ll * tot * (A[i].fi - i + 1) % Mod;
		int v = (1ll * Qsum(1, A[i].se) * inv + 2ll * Qcnt(A[i].se, N) - 1ll * Qsum(A[i].se, N) * inv) % Mod;
		v = (v + Mod) % Mod; ans = Pls(ans, v);
		Mdf2(1ll * (A[i].fi - i) * inv % Mod); Mdf(A[i].se, A[i].fi - i);
	}
	ans = 1ll * ans * inv2 % Mod * tot % Mod;
	printf("%d", ans);
	return 0;
}

提出情報

ジャッジ結果