AT_pakencamp_2022_day2_d Binary Strings

对于一个由 $0$ 和 $1$ 组成、长度为 $N$ 的字符串，满足对于 $1$ 到 $M$ 的每一个整数 $i$，下述条件都成立的字符串个数，求其对 $998244353$ 取模的余数。 - 在第 $L_i$ 位到第 $R_i$ 位之间，存在字符 $C_i$。

输入以下格式，从标准输入读取。 > $N$ $M$ $L_1$ $R_1$ $C_1$ $L_2$ $R_2$ $C_2$ $\vdots$ $L_M$ $R_M$ $C_M$

输出一个整数，表示满足条件的字符串个数对 $998244353$ 取模的余数。

## 子任务 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$ 分）无其他限制 ## 样例解释 1 `010`、`011`、`100`、`101`、`110` 共 $5$ 个字符串符合条件。 ## 样例解释 2 比如 `10101`、`00000` 等，符合条件的字符串共有 $13$ 个。 # 数据范围 - $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)$ - 所有输入均为整数。 由 ChatGPT 5 翻译