luogu#P11346. 「KTSC 2023 R2」会议室 2

「KTSC 2023 R2」会议室 2

题目背景

请勿用 C++14 (GCC 9) 提交。

请在代码开头加入如下代码:

#include<vector>
int count_removals(std::vector<int> S, std::vector<int> E);

题目描述

题目译自 2023년도 국제정보올림피아드 대표학생 선발고사 - 2차 선발고사 T2 「회의실 2

KDH 公司每天会举行 NN 场会议。每场会议都有一个编号,从 00N1N-1。对于每个 ii (0iN1)(0 \leq i \leq N-1),第 ii 场会议在时间 S[i]S[i] 开始,在时间 E[i]E[i] 结束。

KDH 公司安排会议的方式很特别。如果某一天进行的两场不同会议 iijj 满足以下条件之一,则称这两场会议在该天是相关的:

  • 两场会议有重叠的时间段。
  • 存在第三场会议 kk,使得 iijj 都与 kk 相关。

如果两场会议 iijj 在该天不是相关的,则称它们在该天是无关的。KDH 公司在安排会议时,会将每场会议分配到特定的会议室。要求在同一天内,无关的会议不能分配到同一个会议室。KDH 公司会选择满足这些条件的分配方案中所需会议室数量最少的方案。所需的最少会议室数量称为会议的成本。

KDH 公司认为目前的会议安排浪费了太多资源,决定将会议数量减少到只剩一场。为此,KDH 公司将在 N1N-1 天内每天进行以下操作:

  • 选择一个尚未取消的会议。
  • 从当天起永久取消该会议。
  • 进行所有未取消的会议。

当这个过程结束时,除了最后一场会议外,所有会议都被取消。最后剩下的会议是哪一场并不重要。

为了进一步节省成本,KDH 公司希望找到一种方法,使得在 N1N-1 天内每天的总成本最小。你需要计算出有多少种方法可以实现这一目标。两种方法相同的定义是:在 N1N-1 天内每天选择取消的会议完全相同。即使剩下的会议分配方式不同,只要每天取消的会议相同,就认为是相同的方法。由于方法数量可能非常大,结果需要对 10000000071000000007 取模。

你需要实现以下函数:

int count_removals(vector<int> S, vector<int> E);
  • S, E:大小为 NN 的整数数组。对于每个 ii (0iN1)(0 \leq i \leq N-1),第 ii 场会议在时间 S[i]S[i] 开始,在时间 E[i]E[i] 结束。
  • 该函数返回在 N1N-1 天内每天的总成本最小的情况下,选择取消会议的方法数量,对 10000000071000000007 取模。

注意,提交的代码中不应包含任何输入输出操作。

输入格式

示例评测程序按以下格式读取输入:

  • 11 行:NN
  • 2+i2+i (0iN1)(0 \leq i \leq N-1) 行:S[i]E[i]S[i]\,E[i]

输出格式

示例评测程序按以下格式输出:

  • 11 行:函数 count_removals 返回的值
4
1 2
3 4
5 6
7 8
24
10
1 5
2 3
4 7
6 11
8 9
10 15
12 13
14 20
16 17
18 19
13280
10
1 20
2 9
3 4
5 8
6 7
10 17
11 16
12 13
14 15
18 19
845040
10
1 5
2 9
3 10
4 12
6 14
7 16
8 17
11 18
13 19
15 20
1797408
10
12 16
5 7
10 19
2 3
4 6
17 20
8 11
1 15
14 18
9 13
647760

提示

样例 1 解释

考虑 N=4,S=[1,3,5,7],E=[2,4,6,8]N=4, S=[1,3,5,7], E=[2,4,6,8] 的情况。

评测程序将调用如下函数:

count_removals([1,3,5,7], [2,4,6,8]);

无论选择哪种方式取消会议,每天所需的会议室数量(即成本)依次为 332211,总成本为 66。因此,所有方法都是可行的。

函数应返回 24

数据范围

对于所有输入数据,满足:

  • 2N20002 \leq N \leq 2000
  • 对于每个 ii (0iN1)(0 \leq i \leq N-1)1S[i]<E[i]2N1 \leq S[i] < E[i] \leq 2N
  • 对于每个 i,ji,j (0i<jN1)(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]$

详细子任务附加限制及分值如下表所示。

子任务 分值 附加限制
11 33 N10N \leq 10S[0]=1,E[0]=2NS[0]=1, E[0]=2N
22 88 N20N \leq 20
33 3030 N300N \leq 300
44 1212 任意时刻进行的会议最多为 22
55 对于每个 i,ji,j (0i,jN1)(0 \leq i, j \leq N-1),不存在 ij,S[i]<S[j]<E[i]<E[j]i \neq j, S[i] < S[j] < E[i] < E[j]i,ji, j
66 1010 对于每个 i,ji,j (0i,jN1)(0 \leq i, j \leq N-1),不存在 ij,S[i]<S[j]<E[j]<E[i]i \neq j, S[i] < S[j] < E[j] < E[i]i,ji, j
77 2525 无附加限制