← 返回题目列表

Codeforces · 1327/F

F. 和段

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

给定三个整数 $$$n$$$、$$$k$$$、$$$m$$$ 和 $$$m$$$ 条件 $$$(l_1, r_1, x_1), (l_2, r_2, x_2), \dots, (l_m, r_m, x_m)$$$。

计算不同数组 $$$a$$$ 的数量,由 $$$n$$$ 整数组成,使得:

- $$$0 \le a_i < 2^k$$$ 对于每个 $$$1 \le i \le n$$$;
- 对每个 $$$1 \le i \le m$$$ 进行数字 $$$a[l_i] \& a[l_i + 1] \& \dots \& a[r_i] = x_i$$$ 的按位与。

如果存在 $$$i$$$ 使得 $$$a_i \neq b_i$$$ 的位置,则两个数组 $$$a$$$ 和 $$$b$$$ 被视为不同。

这个数字可能非常大,所以打印它对 $$$998244353$$$ 取模。

输入

第一行包含三个整数 $$$n$$$、$$$k$$$ 和 $$$m$$$ ($$$1 \le n \le 5 \cdot 10^5$$$、$$$1 \le k \le 30$$$、$$$0 \le m \le 5 \cdot 10^5$$$) — 数组的长度$$$a$$$,$$$a$$$ 中所有数字都应小于 $$$2^k$$$ 的值和条件数。

接下来的 $$$m$$$ 行包含条件的描述 $$$l_i$$$、$$$r_i$$$ 和 $$$x_i$$$ ($$$1 \le l_i \le r_i \le n$$$, $$$0 \le x_i < 2^k$$$) — 条件段的边界及其上所需的按位 AND 值。

输出

打印一个整数 — 满足所有上述条件的不同数组 $$$a$$$ 的数量以 $$$998244353$$$ 为模。

示例

输入 #1

4 3 2
1 3 3
3 4 6

输出 #1

3

输入 #2

5 2 3
1 3 2
2 5 0
3 3 3

输出 #2

33

注意

这里你可以回忆一下什么是按位与运算。

在第一个示例中,答案是以下数组:$$$[3, 3, 7, 6]$$$、$$$[3, 7, 7, 6]$$$ 和 $$$[7, 3, 7, 6]$$$。