UOJ Logo

NOI.AC

1S 512MB

#117. game

统计

【题目描述】

俄罗斯套娃是一个有趣的游戏。

我们考虑最开始的时候有 $n$ 个套娃,其中第 $i$ 个套娃的大小为 $A[i]$, 内部的空间大小为 $B[i]$,最开始每一个套娃是独立的放在桌面上, 我们可以做多个操作,其中每一个操作我们选择两个套娃 $i$ 和$j$,我们要把第$i$ 个套娃放在第 $j$ 个套娃里面,要保证三个条件

1:第 $i$ 个套娃不在任何其他套娃里面。

2:第$j$ 个套娃里面没有任何套娃。

3:$A[i]$ < $B[j]$。

注意这里$j$ 套娃外面和 $i$ 套娃里面是可以有套娃的。

我们不断合并套娃直到不能操作,我们想要知道最终状态的方案数是多少。答案对 $10^9+7$ 取模。 【输入格式】 输入文件 game.in

第一行一个整数 n。

接下来 $n$ 行,$A[i]$和 $B[i]$,表示第 $i$ 个套娃的大小和内部的空间。 【输出格式】

输出文件 game.out

输出答案对 $10^9+7$ 取模的结果。

【样例输入】

5  
4 3  
3 1  
6 5  
2 1  
4 2

【样例输出】

4 

【样例解释】

1、将套娃 4 放入套娃 3;

2、将套娃 4 放入套娃 1,将套娃 1 放入套娃 3;

3、将套娃 4 放入套娃 1,将套娃 2 放入套娃 3;

4、将套娃 4 放入套娃 1,将套娃 5 放入套娃 3。

【样例 2】

点此下载样例

【数据范围】

对于 $10$%的数据 $n \le 8,0 \le B[i] \le A[i] \le 10$

对于 $50$%的数据 $n \le 30$

对于 $70$%的数据 $n \le 70$

对于 $100$%的数据 $1 \le n \le 300, 0 \le B[i] < A[i] \le (2^31)-1$

对于 $200$%的数据 $n \le 2000$(不计入成绩,AK 后想想怎么做,啊也不难)