← 返回题目列表

Codeforces · 2096/H

H. 精彩的异或问题

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

你是骄傲...没关系,解决这个问题就可以了。

有 $$$n$$$ 间隔 $$$[l_1, r_1], [l_2, r_2], \ldots [l_n, r_n]$$$。对于从 $$$0$$$ 到 $$$2^m - 1$$$ 的每个 $$$x$$$,找到序列 $$$a_1, a_2, \ldots a_n$$$ 的模数 $$$998\,244\,353$$$,使得:

  • $$$l_i \leq a_i \leq r_i$$$ 对于从 $$$1$$$ 到 $$$n$$$ 的所有 $$$i$$$;
  • $$$a_1 \oplus a_2 \oplus \ldots \oplus a_n = x$$$,其中 $$$\oplus$$$ 表示按位异或运算符。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$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 \lt 2^m$$$)。

保证所有测试用例的$$$n$$$总和不超过$$$2 \cdot 10^5$$$,所有测试用例的$$$2^m$$$总和不超过$$$2^{18}$$$。

输出

对于从 $$$0$$$ 到 $$$2^m - 1$$$ 的每个 $$$x$$$,让:

  • $$$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$$$ 本身的值。 不 执行模运算。

示例

输入
复制

4
2 2
0 2
1 3
5 3
3 7
1 3
0 2
1 5
3 6
10 14
314 1592
653 5897
932 3846
264 3383
279 5028
841 9716
939 9375
105 8209
749 4459
230 7816
1 5
0 29

输出
复制

22
9812
75032210
1073741823

注意

对于第一个测试用例,$$$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$$$。