题目描述
求满足限制的长度为 n 的整数序列 a1,…,an 的个数,其中 1≤ai≤s。
有 m 个限制。每个限制是三元组 (l,r,v),要求区间 [l,r] 内至少存在一个位置 i 使 ai=v。也就是说,该区间中的元素不能全部等于 v。
输出合法序列数对 998244353 取模的结果。
输入格式
第一行三个整数 n,m,s。接下来 m 行,每行三个整数 l,r,v,表示一个限制。
输出格式
一行一个整数,表示答案对 998244353 取模后的结果。
样例
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×105,0≤m≤2×105,1≤l≤r≤n,1≤v≤s。
| 子任务 |
分值 |
附加限制 |
| 1 |
10 |
n,m,s≤8 |
| 2 |
20 |
n≤2000,m≤15 |
| 3 |
n,m≤2000 |
| 4 |
10 |
所有限制的 v 均为 1 |
| 5 |
各限制的 v 两两不同 |
| 6 |
30 |
无 |
原 PDF 在子任务 4、5 中将限制值写作 bi,即第 i 个限制的第三个数。
原 PDF 题面