← 返回题目列表

AtCoder · autumn_fest_08

H. 联合国组织

中文机器翻译题面 查看原题

配点

満点
120
部分点
30

問題文

A 君、T 君和 J 先生正在查看地下世界列车各自的运行区间表。J 先生注意到某些运行区间可以排列成金字塔形,并命令 A 君和 T 君调查有多少种排列方法。

现在N给定一个运行区间。从中恰好D个元素组成的运行区间列[ A_1,A_2,...,A_D ],对任意的i=1,...,D-1,(A_iの始点)<(A_{i+1}の始点)和 满足(A_{i+1}の終点)< (A_iの終点)总是成立的那些数量。求不同运行区间列的数量除以314159265的余数。


入力形式

输入按以下格式给出。

N\ D\\
left_1\ right_1\\
left_2\ right_2\\
...\\
left_N\ right_N

N表示运行区间的个数。 left_i是 对于i表示第几号运行区间的起点位置, right_i是 对于i表示第几号运行区间的终点位置。

出力形式

将组合数输出在一行。

制約

  • 2 ≤ N ≤ 100000
  • 2 ≤ D ≤ 15
  • -10^9 ≤ left_i,\ right_i ≤ 10^9
  • left_i < right_i
  • left_i, right_j全部互不相同。
  • 输入值均为整数。

该问题的判定包括,30 点分的测试用例组被设定。这个组中包含的测试用例除了满足上述条件外,还满足以下条件。

  • D=2

入力例 1

3 2
1 7
2 4
8 10

出力例 1

1

如图所示,1第几个运行区间和2第几个运行区间组成的区间序列才满足条件。

図1


入力例 2

5 4
1 10
2 9
3 8
4 7
5 6

出力例 2

5

5从一个到哪几个4选出并排列都能满足条件,C(5,4)=5共有几种方式。

図2


入力例 3

4 2
1 10
2 5
3 4
8 11

出力例 3

3

入力例 4

4 3
1 7
2 8
3 6
4 5

出力例 4

2

作者:uwi