#P6337. 第四道题

    ID: 6423 传统题 1000ms 1024MiB 尝试: 1 已通过: 1 难度: 8 上传者: 标签>CF2400提高+/省选-计数 DP线性 DP消除被支配候选队列滑动窗口

第四道题

题目描述

求满足限制的长度为 nn 的整数序列 a1,…,ana_1,\ldots,a_n 的个数,其中 1≤ai≤s1\le a_i\le s。

有 mm 个限制。每个限制是三元组 (l,r,v)(l,r,v),要求区间 [l,r][l,r] 内至少存在一个位置 ii 使 ai≠va_i\ne v。也就是说,该区间中的元素不能全部等于 vv。

输出合法序列数对 998244353998244353 取模的结果。

输入格式

第一行三个整数 n,m,sn,m,s。接下来 mm 行,每行三个整数 l,r,vl,r,v,表示一个限制。

输出格式

一行一个整数,表示答案对 998244353998244353 取模后的结果。

样例

8 8 3
1 5 1
6 8 2
2 6 2
3 7 1
1 3 3
4 8 1
5 6 3
1 8 2
5291

数据范围

1≤n,s≤2×1051\le n,s\le2\times10^5,0≤m≤2×1050\le m\le2\times10^5,1≤l≤r≤n1\le l\le r\le n,1≤v≤s1\le v\le s。

子任务 分值 附加限制
1 10 n,m,s≤8n,m,s\le8
2 20 n≤2000n\le2000,m≤15m\le15
3 n,m≤2000n,m\le2000
4 10 所有限制的 vv 均为 11
5 各限制的 vv 两两不同
6 30 无

原 PDF 在子任务 4、5 中将限制值写作 bib_i,即第 ii 个限制的第三个数。

原 PDF 题面