我们固定了 A 队中的人数之后一共会有三类人，分别是只能放 A 的，只能放 B 的，和 A 与 B 都能去的，这里可以用差分数组维护。（可以通过当前能去 A 队的人数推出 B 队的范围就是 n−r 到 n−l）
这个时候我们可以通过容斥原理先判断一下当前情况合不合法，然后就是能去两个队的用组合数分配就好啦。
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
60
61
62
63
64
65
66
67
68
69
| #include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 998244353;
int fact[222222], invf[222222];
int fastpow(int a, int b)
{
int res = 1;
while (b) {
if (b & 1) {
res = (res * a) % mod;
}
b >>= 1;
a = (a * a) % mod;
}
return res;
}
void init(int n)
{
fact[0] = 1;
for (int i = 1; i <= n + 1; i++) {
fact[i] = (fact[i - 1] * i) % mod;
}
invf[n + 1] = fastpow(fact[n + 1], mod - 2);
for (int i = n; i >= 0; i--) {
invf[i] = (invf[i + 1] * (i + 1)) % mod;
}
return;
}
int C(int n, int m)
{
return ((fact[n] * invf[m]) % mod * invf[n - m]) % mod;
}
signed main()
{
int n;
cin >> n;
init(n + 111);
vector<int> d1(n + 2, 0), d2(n + 2, 0), d3(n + 2, 0);
for (int i = 0; i < n; i++) {
int l, r;
cin >> l >> r;
d1[l]++;
d1[r + 1]--;
d2[n - r]++;
d2[n - l + 1]--;
int tpl = max(l, n - r), tpr = min(r, n - l);
if (tpl <= tpr) {
d3[tpl]++;
d3[tpr + 1]--;
}
}
int ans = 0;
int cnt1 = 0, cnt2 = 0, cnt3 = 0;
for (int i = 1; i < n; i++) {
cnt1 += d1[i];
cnt2 += d2[i];
cnt3 += d3[i];
if (cnt1 + cnt2 - cnt3 < n)
continue;
int tp = cnt1 - cnt3;
if (tp <= i && i - tp <= cnt3) {
ans = (ans + C(cnt3, i - tp)) % mod;
}
}
cout << ans;
return 0;
}
|
