CF2096H Wonderful XOR Problem

你是...算了，直接解决这个问题吧。 有 $n$ 个区间 $[l_1, r_1], [l_2, r_2], \ldots [l_n, r_n]$。对于每个 $x$ 从 $0$ 到 $2^m - 1$，求满足以下条件的序列 $a_1, a_2, \ldots a_n$ 的数量（模 $998\,244\,353$）： - 对于所有 $i$ 从 $1$ 到 $n$，有 $l_i \leq a_i \leq r_i$； - $a_1 \oplus a_2 \oplus \ldots \oplus a_n = x$，其中 $\oplus$ 表示[按位异或运算符](https://en.wikipedia.org/wiki/Bitwise_operation#XOR)。

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。接下来是每个测试用例的描述。 第一行包含两个整数 $n$ 和 $m$（$1 \leq n \leq 2 \cdot 10^5$，$1 \leq m \leq 18$）。 接下来的 $n$ 行中，第 $i$ 行包含两个整数 $l_i$ 和 $r_i$（$0 \leq l_i \leq r_i < 2^m$）。 保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$，且所有测试用例的 $2^m$ 之和不超过 $2^{18}$。

对于每个 $x$ 从 $0$ 到 $2^m - 1$，定义： - $f_x$ 为有效序列的数量，模 $998\,244\,353$； - $g_x = f_x \cdot 2^x \mod 998\,244\,353$。 这里，$f_x$ 和 $g_x$ 都是区间 $[0, 998\,244\,352]$ 内的整数。 设 $h = g_0 \oplus g_1 \oplus \ldots \oplus g_{2^m - 1}$。 输出一个整数——$h$ 的值本身。不要进行模运算。

对于第一个测试用例，$f_x$ 的值如下： - $f_0 = 2$，因为有 $2$ 个有效序列：$[1, 1]$ 和 $[2, 2]$； - $f_1 = 2$，因为有 $2$ 个有效序列：$[0, 1]$ 和 $[2, 3]$； - $f_2 = 2$，因为有 $2$ 个有效序列：$[0, 2]$ 和 $[1, 3]$； - $f_3 = 3$，因为有 $3$ 个有效序列：$[0, 3]$、$[1, 2]$ 和 $[2, 1]$。 $g_x$ 的值如下： - $g_0 = f_0 \cdot 2^0 = 2 \cdot 2^0 = 2$； - $g_1 = f_1 \cdot 2^1 = 2 \cdot 2^1 = 4$； - $g_2 = f_2 \cdot 2^2 = 2 \cdot 2^2 = 8$； - $g_3 = f_3 \cdot 2^3 = 3 \cdot 2^3 = 24$。 因此，输出的值为 $2 \oplus 4 \oplus 8 \oplus 24 = 22$。 对于第二个测试用例，$f_x$ 的值如下： - $f_{0} = 120$； - $f_{1} = 120$； - $f_{2} = 119$； - $f_{3} = 118$； - $f_{4} = 105$； - $f_{5} = 105$； - $f_{6} = 106$； - $f_{7} = 107$。 翻译由 DeepSeek V3 完成