【agc023E】Inversions

发表于 更新于 本文字数： 4.1k 阅读时长 ≈ 4 分钟
https://agc023.contest.atcoder.jp/tasks/agc023_e

题目链接

【agc023E】Inversions

做法

yyb的题解

考虑计算合法排列的方案数。
记 $ cnt[i] = \sum [ a_j >= i ] $ ，则方案数为 $ tot = \prod_{ i = 1 }^{ n } (cnt[i] (n - i)) $ 。
意思是将数从 n 到 1 填入，对于一个数 i 有 $ cnt[i] $ 个位置可以填，其中 n - i 个位置被占了。显然当方案数为 0 时答案为 0 。

存在一种比较好写的 $ O(n^2 \log n) $ 的做法。考虑枚举两个位置 $ i, j (i < j) $ ，存在三种情况：

  1. $ a_i = a_j $ 。显然如果存在一种方案合法，则这两个位置的数对换也合法，逆序对数为总方案数的一半。
  2. $ a_i < a_j $ 。显然只有 $ a_j = a_i $ 的部分是有用的，即 $ j $ 处方案数为（总方案数 - $ a_j \in [a_i + 1, a_j] $ 的方案数）/ 2。
  3. 总排列数减不合法，相当于是要求 $ p_i < p_j $ 的方案数。无非是把上面的 $ i, j $ 互换了而已，计算方法还是一样的。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7, inv2 = (mod + 1) / 2;
const int N = 200010;
int n, a[N], cnt[N], tot = 1, ans;
int tr[2][N * 4];

inline int add(const int &x, const int &y) {
	return x + y < mod ? x + y : x + y - mod;
}
inline int sub(const int &x, const int &y) {
	return x - y < 0 ? x - y + mod : x - y;
}
inline int mul(const int &x, const int &y) { return (int)((ll)x * y % mod); }
int ksm(int x, int y = mod - 2) {
	int ss = 1; for(; y; y >>= 1, x = mul(x, x)) if(y & 1) ss = mul(ss, x);
	return ss;
}
void build(int u, int l, int r) {
	if(l >= r) {
		tr[0][u] = cnt[l] - (n - l), tr[1][u] = cnt[l] - (n - l + 1);
		return ;
	}
	int mid = (l + r) >> 1;
	build(u * 2, l, mid), build(u * 2 + 1, mid + 1, r);
	tr[0][u] = mul(tr[0][u * 2], tr[0][u * 2 + 1]);
	tr[1][u] = mul(tr[1][u * 2], tr[1][u * 2 + 1]);
}
int ask(int u, int l, int r, int L, int R, int w) {
	if(L <= l && r <= R) return tr[w][u];
	int mid = (l + r) >> 1, res = 1;
	if(L <= mid) res = mul(res, ask(u * 2, l, mid, L, R, w));
	if(R > mid) res = mul(res, ask(u * 2 + 1, mid + 1, r, L, R, w));
	return res;
}
int main() {
	scanf("%d", &n);
	for(int i = 1; i <= n; i++) scanf("%d", &a[i]), ++cnt[a[i]];
	for(int i = n; i; i--) cnt[i] += cnt[i + 1];
	for(int i = n; i; i--) tot = mul(tot, sub(cnt[i], n - i));
	if(!tot) { puts("0"); return 0; }
	build(1, 1, n);
	for(int i = 1; i < n; i++) for(int j = i + 1; j <= n; j++) {
		if(a[i] == a[j]) ans = add(ans, mul(tot, inv2));
		else if(a[i] < a[j]) {
			int ss = mul(tot, ksm(ask(1, 1, n, a[i] + 1, a[j], 0)));
			ss = mul(ss, ask(1, 1, n, a[i] + 1, a[j], 1));
			ans = add(ans, mul(ss, inv2));
		}
		else {
			int ss = mul(tot, ksm(ask(1, 1, n, a[j] + 1, a[i], 0)));
			ss = mul(ss, ask(1, 1, n, a[j] + 1, a[i], 1));
			ss = sub(tot, mul(ss, inv2)), ans = add(ans, ss);
		}
	}
	printf("%d\n", ans);
	return 0;
}

记 $ D[i] = \frac{ cnt[j] - 1 - (n - j) }{ cnt[j] - (n - j) } $ 。那么枚举一对 $ i, j $ ，它们的贡献是
$$ tot \times \prod_{ k=a_i + 1 }^{ a_j } D[k] = tot \times \frac{ \prod_{ k = 1 }^{ a_j }D[k] }{ \prod_{ k = 1 }^{ a_i } D[k] } $$
树状数组维护前缀和即可。
注意下 $ D[i] $ 可能为 $ 0 $ ，所以求的时候要分段计算一下贡献就好了。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7, inv2 = (mod + 1) / 2;
const int N = 200010;
int n, a[N], cnt[N], tot = 1, ans;
int tr[2][N], up[N], dn[N], zr[N], idn[N];

inline int add(const int &x, const int &y) {
	return x + y < mod ? x + y : x + y - mod;
}
inline int sub(const int &x, const int &y) {
	return x - y < 0 ? x - y + mod : x - y;
}
inline int mul(const int &x, const int &y) { return (int)((ll)x * y % mod); }
int ksm(int x, int y = mod - 2) {
	int ss = 1; for(; y; y >>= 1, x = mul(x, x)) if(y & 1) ss = mul(ss, x);
	return ss;
}
void Add(int x, int w) {
	for(; x <= n; x += x & -x)
		tr[0][x] = add(tr[0][x], w), tr[1][x] = add(tr[1][x], 1);
}
int Ask(int x, int w) {
	int ss = 0; for(; x; x -= x & -x) ss = add(ss, tr[w][x]); return ss;
}
int main() {
	scanf("%d", &n);
	for(int i = 1; i <= n; i++) scanf("%d", &a[i]), ++cnt[a[i]];
	for(int i = n; i; i--) cnt[i] += cnt[i + 1];
	for(int i = n; i; i--)
		tot = mul(tot, sub(cnt[i], n - i)), cnt[i] -= n - i;
	if(!tot) { puts("0"); return 0; }
	up[0] = dn[0] = 1;
	for(int i = 1, x; i <= n; i++) {
		x = mul(cnt[i] - 1, ksm(cnt[i]));
		if(!x) zr[i] = zr[i - 1] + 1, up[zr[i]] = i, dn[i] = dn[i - 1];
		else zr[i] = zr[i - 1], dn[i] = mul(dn[i - 1], x);
		idn[i] = ksm(dn[i]);
	}
	for(int i = 1, x; i <= n; i++) {
		x = sub(Ask(a[i], 0), Ask(up[zr[a[i]]] - 1, 0));
		x = mul(x, mul(dn[a[i]], mul(tot, inv2)));
		ans = add(ans, x);
		Add(a[i], idn[a[i]]);
	}
	for(int i = 1; i <= n; i++) tr[0][i] = tr[1][i] = 0;
	for(int i = n, x; i; i--) {
		x = sub(Ask(a[i] - 1, 0), Ask(up[zr[a[i]]] - 1, 0));
		x = mul(x, mul(dn[a[i]], mul(tot, inv2)));
		ans = sub(ans, x);
		ans = add(ans, mul(Ask(a[i] - 1, 1), tot));
		Add(a[i], idn[a[i]]);
	}
	printf("%d\n", ans);
	return 0;
}