← 返回题目列表

Codeforces · 1119/H

H. 三重

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

您已收到生日礼物 — $$$n$$$ 整数的三倍!其中第 $$$i$$$ 是 $$$\lbrace a_{i}, b_{i}, c_{i} \rbrace$$$。所有数字都大于或等于 $$$0$$$,并且严格小于 $$$2^{k}$$$,其中 $$$k$$$ 是固定整数。

有一天,你玩三元组感到很累。于是你想出了三个新整数$$$x$$$、$$$y$$$、$$$z$$$,然后组成了$$$n$$$数组。第 $$$i$$$ 数组由重复 $$$x$$$ 次的 $$$a_i$$$ 、重复 $$$y$$$ 次的 $$$b_i$$$ 和重复 $$$z$$$ 次的 $$$c_i$$$ 组成。因此,每个数组的长度为$$$(x + y + z)$$$。

您希望从每个数组中精确选择一个整数,使得它们的 XOR(按位异或)等于 $$$t$$$。输出为 $$$0$$$ 和 $$$2^{k} - 1$$$(含)之间的每个 $$$t$$$ 选择数字的方法数,以 $$$998244353$$$ 为模。

输入

第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \leq n \leq 10^{5}$$$, $$$1 \leq k \leq 17$$$) — 数组的数量和所有数字的二进制长度。

第二行包含三个整数 $$$x$$$、$$$y$$$、$$$z$$$ ($$$0 \leq x,y,z \leq 10^{9}$$$) — 您选择的整数。

然后是 $$$n$$$ 行。其中第 $$$i$$$ 包含三个整数 $$$a_{i}$$$、$$$b_{i}$$$ 和 $$$c_{i}$$$ ($$$0 \leq a_{i} , b_{i} , c_{i} \leq 2^{k} - 1$$$) - 构成第 $$$i$$$ 数组的整数。

输出

打印包含 $$$2^{k}$$$ 整数的单行。其中第 $$$i$$$ 应该是从每个数组中精确选择一个整数的方法数,以便它们的 XOR 等于 $$$t = i-1$$$ 模 $$$998244353$$$。

示例

输入 #1

1 1
1 2 3
1 0 1

输出 #1

2 4

输入 #2

2 2
1 2 1
0 1 2
1 2 3

输出 #2

4 2 4 6

输入 #3

4 3
1 2 3
1 3 7
0 2 5
1 0 6
3 3 2

输出 #3

198 198 126 126 126 126 198 198

注意

在第一个例子中,我们形成的数组是$$$(1, 0, 0, 1, 1, 1)$$$,我们有两种选择来得到$$$0$$$作为XOR,四种选择来得到$$$1$$$。

在第二个示例中,两个数组是 $$$(0, 1, 1, 2)$$$ 和 $$$(1, 2, 2, 3)$$$。总共有十六个$$$(4 \cdot 4)$$$选项,其中$$$4$$$($$$1 \oplus 1$$$和$$$2 \oplus 2$$$,每个选项两个)给出$$$0$$$,$$$2$$$其中($$$0 \oplus 1$$$和$$$2 \oplus 3$$$)给出$$$1$$$,其中 $$$4$$$($$$0 \oplus 2$$$ 和 $$$1 \oplus 3$$$,各两个选项)给出 $$$2$$$,最后 $$$6$$$ 其中($$$0 \oplus 3$$$、$$$2 \oplus 1$$$ 和 $$$1 \oplus 2$$$ 的四个选项)给出 $$$3$$$。