CF1119H Triple

题目描述

你收到了生日礼物——$n$ 个整数三元组！第 $i$ 个三元组为 $\lbrace a_{i}, b_{i}, c_{i} \rbrace$。所有数字都大于等于 $0$，且严格小于 $2^{k}$，其中 $k$ 是一个固定的整数。

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

你想从每个数组中恰好选出一个整数，使得它们的异或和（按位异或）等于 $t$。请输出对于每个 $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$ 行，每行包含三个整数 $a_{i}$、$b_{i}$、$c_{i}$（$0 \leq a_{i}, b_{i}, c_{i} \leq 2^{k} - 1$）——构成第 $i$ 个数组的整数。

输出格式

输出一行共 $2^{k}$ 个整数。第 $i$ 个数表示恰好选出一个数使异或和为 $t = i-1$ 的方案数，对 $998244353$ 取模。

输入输出样例 #1

输入 #1

1 1
1 2 3
1 0 1

输出 #1

2 4 

输入输出样例 #2

输入 #2

2 2
1 2 1
0 1 2
1 2 3

输出 #2

4 2 4 6 

输入输出样例 #3

输入 #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$，有四种方式使异或和为 $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$。

由 ChatGPT 4.1 翻译