← 返回题目列表

AtCoder · pakencamp_2022_day2_d

D. 二进制字符串

中文机器翻译题面 查看原题

配点 : 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)
  • 所有输入均为整数

小課題

  1. (50 点) N\leq 16, M\leq 16
  2. (100 点) N\leq 2000, M\leq 2000, C_i=0\,(1\leq i\leq M)
  3. (150 点) C_i=0\,(1\leq i\leq M)
  4. (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