DDOSvoid's Blog

CF 1420D Rescue Nibel!

发表于 分类于
本文字数： 1.5k 阅读时长 ≈ 1 分钟

题目描述

https://codeforces.com/contest/1420/problem/D

Solution

完了，我连最简单的计数都不会了

注意到区间的交如果不为空，那么一定有至少一个区间的左端点与交集的左端点重合，至少一个区间的右端点与交集的右端点重合

我们考虑固定交集的左端点 $i$，我们令 $sum[i]$ 表示包含点 $i$ 的区间个数，$num[i]$ 表示左端点为 $i$ 的区间个数

那么 $num[i]$ 中的区间至少要选一个，所以答案就是 $\binom{sum[i]}{k}-\binom{sum[i]-num[i]}{k}$

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
#include <iostream>
#include <cstdio>
#include <algorithm>
#define maxn 300010
#define ll long long
using namespace std;

const int p = 998244353;

ll pow_mod(ll x, ll n) {
    ll s = 1;
    for (; n; n >>= 1) {
        if (n & 1) s = s * x % p;
        x = x * x % p;
    }
    return s;
}

int n, m;

ll inv[maxn], fac[maxn];
ll C(int n, int m) {
    if (n < m) return 0;
    return fac[n] * inv[m] % p * inv[n - m];
} 

struct node {
    int l, r;
} a[maxn];

int b[maxn * 2], cnt; 
void init_hash() {
    for (int i = 1; i <= n; ++i) b[i] = a[i].l, b[i + n] = a[i].r;
    sort(b + 1, b + 2 * n + 1); cnt = unique(b + 1, b + 2 * n + 1) - b - 1; 
    for (int i = 1; i <= n; ++i) {
        a[i].l = lower_bound(b + 1, b + cnt + 1, a[i].l) - b;
        a[i].r = lower_bound(b + 1, b + cnt + 1, a[i].r) - b;
    }
}

int sum[2 * maxn], num[2 * maxn];

ll ans; 
int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) cin >> a[i].l >> a[i].r;
    init_hash();
    fac[0] = 1; for (int i = 1; i <= n; ++i) fac[i] = fac[i - 1] * i % p;
    inv[n] = pow_mod(fac[n], p - 2); for (int i = n - 1; ~i; --i) inv[i] = inv[i + 1] * (i + 1) % p; 
    for (int i = 1; i <= n; ++i) ++sum[a[i].l], --sum[a[i].r + 1], ++num[a[i].l];
    for (int i = 1; i <= cnt; ++i) sum[i] += sum[i - 1];
    for (int i = 1; i <= cnt; ++i) ans = (ans + C(sum[i], m) - C(sum[i] - num[i], m)) % p;
    cout << (ans + p) % p << endl; 
    return 0;
}