配点
- 満点
- 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