#P10332. 彻底起飞

    ID: 9450 传统题 1000ms 256MiB 尝试: 3 已通过: 2 难度: 9 上传者: 标签>CF2800省选/NOI-阈值二值化子集 DP计数 DP子集卷积乘法分配律状态维度消除补集计数子掩码递推 (s-1)&mask组合数乘法递推滚动数组

彻底起飞

题目描述

给定 mm 条比较交换指令。对任意长度为 nn、每个元素都在 [1,L][1,L] 的整数序列 P=(p1,…,pn)P=(p_1,\ldots,p_n),按输入顺序执行全部指令。第 ii 条指令给出 xi,yix_i,y_i。若当前第 xix_i 个元素严格大于第 yiy_i 个元素,交换两者,否则不操作。

若执行结束后序列没有变成非递减序列,则原序列 PP 的权值需要计入答案。定义

$$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\}.$$

其中 [pi=pj][p_i=p_j] 在等式成立时为 11,否则为 00。位运算按从左到右的顺序执行。因此,同奇偶的两个位置且原值相等时,该有序对贡献因子 ijij。乘积包含 i=ji=j。

求所有无法被这些指令正确排序的原序列的权值和,对 109+710^9+7 取模。

输入格式

第一行三个正整数 m,n,Lm,n,L。接下来 mm 行,每行两个整数 xi,yix_i,y_i。

输出格式

输出一行一个整数,表示所求权值和对 109+710^9+7 取模后的结果。

样例 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≤xi,yi≤n1\le x_i,y_i\le n。

原子任务 分值 nn 上界 mm 上界 LL 上界
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 秒。

原 PDF 题面