#PQJ1543x8325. QOJ 1543_8325
QOJ 1543_8325
NOI2024 联合省选 第二试重塑时光(timeline) 重塑时光(timeline) 【题目描述】 小T 正在研究某段时间中所发生的事件。经观测,有n 个编号为1 ∼n 的事件在 这段时间内按顺序依次发生,第i 个发生的是事件pi。这个描述事件发生顺序的排列p 可称为这段时间的.时.间.线。 突然,邪恶生物小S 攻击了这条时间线,将这n 个事件的发生顺序p 变为了在所 有长为n 的排列中等概率随机选取的一个排列。不仅如此,小S 还用剪刀把时间线剪 断,通过进行k 次操作,将排列p 分割成了(k + 1) 段。 具体而言,在小S 进行第i 次操作时,排列p 和之前所有插入的剪断点构成了一 个长度为(n + i −1) 的序列。该序列包括所有相邻元素之间和序列开头、末尾处共有 (n + i) 个插入位置。小S 将从这些插入位置中等概率随机选取一个位置,插入一个新 的剪断点。最后,小S 从最终被插入的k 个剪断点处把序列剪开,将排列p 分割成了 (k + 1) 段序列。这(k + 1) 段序列中可能有空序列。 为了拯救这条即将毁灭的时间线,小T 决定把这(k + 1) 段序列按某种顺序重新拼 接成一个长度为n 的排列,形成一条新的时间线。不过,由于事件之间存在一定的逻辑 关系,事件的发生时间之间也存在一些先后顺序要求。经研究,共存在m 条先后顺序 要求(u, v),要求事件u 的发生时间必须在事件v 之前。也就是说,u 在时间线中的出 现位置必须在v 之前。 请你设计程序,计算有多大的概率,存在至少一种重新排列这(k + 1) 段序列,并 将其重新拼接为一条新的时间线的方案,能够使所有的m 条事件发生时间之间的先后 顺序要求都得到满足。 为了避免精度误差,请你输出答案对109 +7 取模的结果。形式化地,可以证明答案 可被表示为一最简分数p q,请你输出一个x 满足0 ≤x < 109+7 且qx ≡p mod (109+7)。 可以证明在题目条件下这样的x 总是存在。 【输入格式】 从文件timeline.in 中读入数据。 第一行三个整数n, m, k,分别描述事件的个数,事件之间先后顺序的条数以及小S 进行的剪断操作次数。 接下来m 行,每行两个整数u, v,表示一条事件发生时间的先后顺序要求。 【输出格式】 输出到文件timeline.out 中。 输出一行一个整数,表示所求答案。 第5 页 共12 页
NOI2024 联合省选 第二试重塑时光(timeline) 【样例1 输入】 1 2 1 1 2 1 2 【样例1 输出】 1 666666672 【样例1 解释】 假如事件1 的发生时间早于事件2,那么无论怎样拼接都是可行方案,一定可以满 足要求。否则,只有剪断时间线的位置位于事件1 和事件2 的发生时间之间,才能满足 要求。答案为1 2 + 1 2 × 1 3 = 2 3。 【样例2 输入】 1 3 0 2 第6 页 共12 页
NOI2024 联合省选 第二试重塑时光(timeline) 【样例2 输出】 1 1 【样例2 解释】 没有任何事件发生时间之间的先后顺序要求,因此无论怎样拼接都是可行的方案, 答案为1。 【样例3 输入】 1 4 4 4 2 1 2 3 1 3 4 1 4 5 2 4 【样例3 输出】 1 937500007 【样例4】 见选手目录下的timeline/timeline4.in 与timeline/timeline4.ans。 【样例5】 见选手目录下的timeline/timeline5.in 与timeline/timeline5.ans。 该组样例满足数据范围中的特殊性质B。 【样例6】 见选手目录下的timeline/timeline6.in 与timeline/timeline6.ans。 该组样例满足数据范围中的特殊性质A。 【样例7】 见选手目录下的timeline/timeline7.in 与timeline/timeline7.ans。 第7 页 共12 页
NOI2024 联合省选 第二试重塑时光(timeline) 【子任务】 对于所有测试数据, • 1 ≤n ≤15, • 0 ≤m ≤n(n−1) 2 ,0 ≤k ≤n, • 1 ≤u < v ≤n,保证不存在两对(u, v) 完全相同。 测试点 n m k 特殊性质 1 ≤3 = n −1 = 0 B 2 ≤5 ≤n(n−1) 2 ≤n 无 3, 4 ≤14 = n −1 B 5 = 0 A 6 ≤n 7 = 0 无 8 = n(n−1) 2 9, 10 ≤9 ≤15 11 ≤13 ≤n(n−1) 2 = 0 12 ≤n 13 ∼17 ≤14 18 ∼20 ≤15 特殊性质A:对于每个事件x,至多存在一条先后顺序(u, v) 使得v = x。 特殊性质B:对于所有先后顺序(u, v),均满足u = 1。 第8 页 共12 页