配点 : 600 点
問題文
0 和
按字典顺序比较 1 组成 N 是一串 1 以上 M 以下所有整数
对于 i ,计算满足以下条件的项目数。
除以 998244353 求余数。
- L_i 从第一个字符开始 R_i 字符之间的字符 C_i 存在
制約
- 1\leq N\leq 2\times 10^5
- 1\leq M\leq 2\times 10^5
- 1\leq L_i\leq R_i\leq N\,(1\leq i\leq M)
- C_i\in\lbrace 0,1\rbrace\,(1\leq i\leq M)
- 所有输入均为整数
小課題
- (50 点) N\leq 16, M\leq 16
- (100 点) N\leq 2000, M\leq 2000, C_i=0\,(1\leq i\leq M)
- (150 点) C_i=0\,(1\leq i\leq M)
- (300 点)无附加约束
入力
输入是按以下格式从标准输入给出的。
N M L_1 R_1 C_1 L_2 R_2 C_2 \vdots L_M R_M C_M
出力
答案 行 1 行输出。
入力例 1
3 2 1 3 0 1 2 1
出力例 1
5
010、011、100、101、110 的
合并 5 是满足条件的字符串。
总计如
入力例 2
5 4 1 2 0 2 3 0 3 4 0 4 5 0
出力例 2
13
10101 或 00000 等总计 13 字符串满足条件。
入力例 3
7 9 4 6 0 1 2 0 5 7 1 3 4 0 7 7 0 6 7 1 2 5 1 3 5 0 1 7 1
出力例 3
13