bzoj#P3688. 折线统计

折线统计

题目描述

二维平面上有 nn 个点 (xi,yi)(x_i,y_i),现在这些点中取若干点构成一个集合 SS,对它们按照 xx 坐标排序,顺次连接,将会构成一些连续上升、下降的折线,设其数量为 f(S)f(S)。如下图中,12,23,35,561\to 2,2\to 3,3\to 5,5\to 6(数字为下图中从左到右的点编号),将折线分为了 44 部分,每部分连续上升、下降。

现给定 kk,求满足 f(S)=kf(S)=kSS 集合个数。

输入格式

第一行两个整数 nnkk,以下 nn 行每行两个数 (xi,yi)(xi,yi) 表示第 ii 个点的坐标。所有点的坐标值都在 [1,100000][1,100000] 内,且不存在两个点,xx 坐标值相等或 yy 坐标值相等。

输出格式

输出满足要求的方案总数mod100007\mod 100007 的结果。

5 1
5 5
3 2
4 4
2 3
1 1
19

数据规模与约定

对于 100%100\% 的数据,n50000,0<k10n\le 50000,0<k\le 10