#P10332. 彻底起飞
彻底起飞
题目描述
给定 条比较交换指令。对任意长度为 、每个元素都在 的整数序列 ,按输入顺序执行全部指令。第 条指令给出 。若当前第 个元素严格大于第 个元素,交换两者,否则不操作。
若执行结束后序列没有变成非递减序列,则原序列 的权值需要计入答案。定义
$$f(P)=\prod_{i=1}^{n}\prod_{j=1}^{n} \max\!\left\{[p_i=p_j]\left(\left((i\operatorname{xor}1)\operatorname{xor}j\right)\operatorname{and}1\right)ij,\ 1\right\}.$$其中 在等式成立时为 ,否则为 。位运算按从左到右的顺序执行。因此,同奇偶的两个位置且原值相等时,该有序对贡献因子 。乘积包含 。
求所有无法被这些指令正确排序的原序列的权值和,对 取模。
输入格式
第一行三个正整数 。接下来 行,每行两个整数 。
输出格式
输出一行一个整数,表示所求权值和对 取模后的结果。
样例 1
3 3 19
1 1
1 2
2 3
75924
样例 2
6 4 19
1 1
1 2
1 3
1 4
2 3
4 4
282519360
原题另外在下发文件中提供样例 3。
数据范围
所有指令满足 。
| 原子任务 | 分值 | 上界 | 上界 | 上界 |
|---|---|---|---|---|
| 1 | 10 | 6 | 15 | 6 |
| 2 | 9 | 40 | 9 | |
| 3 | 5 | 14 | 100 | 2 |
| 4 | 25 | 20 | ||
| 5 | 20 | 17 | 80 | |
| 6 | 30 | 18 | 100 | 300 |
原赛第 5 包时限为 2 秒。本站当前评测配置统一为 1 秒。