#P13946. CF1119H Triple

CF1119H Triple

CF1119H Triple

题目描述

你收到了生日礼物——nn 个整数三元组!第 ii 个三元组为 {ai,bi,ci}\lbrace a_{i}, b_{i}, c_{i} \rbrace。所有数字都大于等于 00,且严格小于 2k2^{k},其中 kk 是一个固定的整数。

有一天,你玩三元组玩累了,于是你想出了三个新整数 xx、yy、zz,然后构造了 nn 个数组。第 ii 个数组由 aia_i 重复 xx 次、bib_i 重复 yy 次、cic_i 重复 zz 次组成。因此,每个数组的长度为 x+y+zx + y + z。

你想从每个数组中恰好选出一个整数,使得它们的异或和(按位异或)等于 tt。请输出对于每个 tt 从 00 到 2k−12^{k} - 1,恰好选出一个数使异或和为 tt 的方案数,结果对 998244353998244353 取模。

输入格式

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

第二行包含三个整数 xx、yy、zz(0≤x,y,z≤1090 \leq x, y, z \leq 10^{9})——你选择的整数。

接下来 nn 行,每行包含三个整数 aia_{i}、bib_{i}、cic_{i}(0≤ai,bi,ci≤2k−10 \leq a_{i}, b_{i}, c_{i} \leq 2^{k} - 1)——构成第 ii 个数组的整数。

输出格式

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

输入输出样例 #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)(1, 0, 0, 1, 1, 1),有两种方式使异或和为 00,有四种方式使异或和为 11。

在第二个样例中,两个数组分别为 (0,1,1,2)(0, 1, 1, 2) 和 (1,2,2,3)(1, 2, 2, 3)。一共有十六种选择(4⋅44 \cdot 4),其中 44 种(1⊕11 \oplus 1 和 2⊕22 \oplus 2,每种各有两种方式)异或和为 00,22 种(0⊕10 \oplus 1 和 2⊕32 \oplus 3)异或和为 11,44 种(0⊕20 \oplus 2 和 1⊕31 \oplus 3,每种各有两种方式)异或和为 22,最后 66 种(0⊕30 \oplus 3、2⊕12 \oplus 1 以及 1⊕21 \oplus 2 的四种方式)异或和为 33。

由 ChatGPT 4.1 翻译