Codeforces 689E Mike and Geometry Problem

发表于 分类于 Disqus：

链接

传送门

题意

给出\(n\)个区间，问所有选择\(k\)个不同区间的方法下它们相交区间的长度和。

思路

离散化之后用扫描线维护有多少个区间包含当前子区间，然后当前区间的贡献为\({num \choose k} \cdot len\)。

代码

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
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;

const LL mod = 1000000007;
const int maxn = 200010;
int l[maxn], r[maxn];
int Hash[maxn << 1], sum[maxn << 1];
LL inv[maxn], fac[maxn], invfac[maxn];

LL C(int n, int k) {
  return fac[n] * invfac[k] % mod * invfac[n - k] % mod;
}

int main() {
  int n, k;
  scanf("%d%d", &n, &k);
  int num = 0;
  inv[1] = fac[1] = fac[0] = invfac[1] = invfac[0] = 1;
  for (int i = 2; i <= n; ++i) {
    inv[i] = (mod - mod / i) * inv[mod % i] % mod;
    fac[i] = fac[i - 1] * i % mod;
    invfac[i] = invfac[i - 1] * inv[i] % mod;
  }
  for (int i = 0; i < n; ++i) {
    scanf("%d%d", &l[i], &r[i]);
    Hash[num++] = l[i];
    Hash[num++] = r[i] + 1;
  }
  sort(Hash , Hash + num);
  num = int(unique(Hash, Hash + num) - Hash);
  for (int i = 0; i < n; ++i) {
    ++sum[int(lower_bound(Hash, Hash + num, l[i]) - Hash)];
    --sum[int(lower_bound(Hash, Hash + num, r[i] + 1) - Hash)];
  }
  int tmp = sum[0];
  LL ans = 0;
  for (int i = 1; i < num; ++i) {
    if (tmp >= k) {
      ans = (ans + C(tmp, k) * (Hash[i] - Hash[i - 1])) % mod;
    }
    tmp += sum[i];
  }
  printf("%lld\n", ans);
  return 0;
}
相关文章