#P10760. 澳洲袋鼠

    ID: 9878 传统题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 8 上传者: 标签>CF2500提高+/省选-二分图建模计数 DP滚动数组二分查找乘法原理排列数计算

澳洲袋鼠

题目描述

澳洲猴和澳洲袋鼠做一个游戏。第 ii 只袋鼠的体积为 AiA_i,袋子的容量为 BiB_i。袋鼠的袋子装入其他袋鼠后,这只袋鼠的体积仍为 AiA_i。

一次操作可以把袋鼠 ii 放入袋鼠 jj 的袋子,条件如下。

  • 袋鼠 ii 目前没有装在其他袋鼠的袋子里。
  • 袋鼠 jj 的袋子目前为空。
  • Ai<BjA_i<B_j。

澳洲猴会一直操作,直到无法进行任何一次操作。求可能的最终状态数量,对 109+710^9+7 取模。直接包含关系完全相同的两个状态视为同一种状态。

输入格式

第一行一个整数 nn。接下来 nn 行,第 ii 行包含两个整数 Ai,BiA_i,B_i,分别表示第 ii 只袋鼠的体积和袋子容量。

输出格式

输出一行一个整数,表示最终状态总数对 109+710^9+7 取模后的结果。

5
4 3
3 1
6 5
2 1
4 2
4

样例说明

四种最终状态的直接包含关系如下,i→ji\to j 表示袋鼠 ii 在袋鼠 jj 的袋子里。

  1. 4→34\to3。
  2. 4→14\to1,1→31\to3。
  3. 4→14\to1,2→32\to3。
  4. 4→14\to1,5→35\to3。

数据规模与约定

  • 对于 50%50\% 的数据,n≤30n\le30。
  • 对于 70%70\% 的数据,n≤70n\le70。
  • 对于 100%100\% 的数据,1≤n≤3001\le n\le300,1≤Bi<Ai≤1091\le B_i<A_i\le 10^9。

原附件末行将体积与袋子容量的不等式写反。上面的不等式与附件正文、样例和评测输入一致。