P11346 [KTSC 2023 R2] 会议室 2

**请勿用 C++14 (GCC 9) 提交。** 请在代码开头加入如下代码： ```cpp #include int count_removals(std::vector S, std::vector E); ```

**题目译自 [2023년도 국제정보올림피아드 대표학생 선발고사 - 2차 선발고사](https://www.ioikorea.kr/archives/ioitst/2023/) T2 「[회의실 2](https://assets.ioikorea.kr/ioitst/2023/2/meeting2/meeting2_statement.pdf)」** KDH 公司每天会举行 $N$ 场会议。每场会议都有一个编号，从 $0$ 到 $N-1$。对于每个 $i$ $(0 \leq i \leq N-1)$，第 $i$ 场会议在时间 $S[i]$ 开始，在时间 $E[i]$ 结束。 KDH 公司安排会议的方式很特别。如果某一天进行的两场不同会议 $i$ 和 $j$ 满足以下条件之一，则称这两场会议在该天是相关的： - 两场会议有重叠的时间段。 - 存在第三场会议 $k$，使得 $i$ 和 $j$ 都与 $k$ 相关。 如果两场会议 $i$ 和 $j$ 在该天不是相关的，则称它们在该天是无关的。KDH 公司在安排会议时，会将每场会议分配到特定的会议室。要求在同一天内，无关的会议不能分配到同一个会议室。KDH 公司会选择满足这些条件的分配方案中所需会议室数量最少的方案。所需的最少会议室数量称为会议的成本。 KDH 公司认为目前的会议安排浪费了太多资源，决定将会议数量减少到只剩一场。为此，KDH 公司将在 $N-1$ 天内每天进行以下操作： - 选择一个尚未取消的会议。 - 从当天起永久取消该会议。 - 进行所有未取消的会议。 当这个过程结束时，除了最后一场会议外，所有会议都被取消。最后剩下的会议是哪一场并不重要。 为了进一步节省成本，KDH 公司希望找到一种方法，使得在 $N-1$ 天内每天的总成本最小。你需要计算出有多少种方法可以实现这一目标。两种方法相同的定义是：在 $N-1$ 天内每天选择取消的会议完全相同。即使剩下的会议分配方式不同，只要每天取消的会议相同，就认为是相同的方法。由于方法数量可能非常大，结果需要对 $1000000007$ 取模。 你需要实现以下函数： ```cpp int count_removals(vector S, vector E); ``` - `S, E`：大小为 $N$ 的整数数组。对于每个 $i$ $(0 \leq i \leq N-1)$，第 $i$ 场会议在时间 $S[i]$ 开始，在时间 $E[i]$ 结束。 - 该函数返回在 $N-1$ 天内每天的总成本最小的情况下，选择取消会议的方法数量，对 $1000000007$ 取模。 注意，提交的代码中不应包含任何输入输出操作。

示例评测程序按以下格式读取输入： - 第 $1$ 行：$N$ - 第 $2+i$ $(0 \leq i \leq N-1)$ 行：$S[i]\,E[i]$

示例评测程序按以下格式输出： - 第 $1$ 行：函数 `count_removals` 返回的值

### 样例 1 解释 考虑 $N=4, S=[1,3,5,7], E=[2,4,6,8]$ 的情况。 评测程序将调用如下函数： ```cpp count_removals([1,3,5,7], [2,4,6,8]); ``` 无论选择哪种方式取消会议，每天所需的会议室数量（即成本）依次为 $3$、$2$、$1$，总成本为 $6$。因此，所有方法都是可行的。 函数应返回 `24`。 ### 数据范围 对于所有输入数据，满足： - $2 \leq N \leq 2000$ - 对于每个 $i$ $(0 \leq i \leq N-1)$，$1 \leq S[i] < E[i] \leq 2N$ - 对于每个 $i,j$ $(0 \leq i < j \leq N-1)$，$S[i] \neq S[j], S[i] \neq E[j], E[i] \neq S[j], E[i] \neq E[j]$ 详细子任务附加限制及分值如下表所示。 | 子任务 | 分值 | 附加限制 | | :-: | :-: | :-: | | $1$ | $3$ | $N \leq 10$；$S[0]=1, E[0]=2N$ | | $2$ | $8$ | $N \leq 20$ | | $3$ | $30$ | $N \leq 300$ | | $4$ | $12$ | 任意时刻进行的会议最多为 $2$ 场 | | $5$ | $12$ | 对于每个 $i,j$ $(0 \leq i, j \leq N-1)$，不存在 $i \neq j, S[i] < S[j] < E[i] < E[j]$ 的 $i, j$ 对 | | $6$ | $10$ | 对于每个 $i,j$ $(0 \leq i, j \leq N-1)$，不存在 $i \neq j, S[i] < S[j] < E[j] < E[i]$ 的 $i, j$ 对 | | $7$ | $25$ | 无附加限制 |