Triple

题意翻译

你的生日礼物是$n$个整数三元组。第$i$个三元组是$\{a_i,b_i,c_i\}$,所有数字$j$都满足$0\le j<2^k$,$k$是一个固定的数字，将由题目输入。 一天，你玩三元组玩腻了，所以你有了3个新的整数$x,y,z$,然后填充了$n$个数组。第$i$个数组有$x$个$a_i$,$y$个$b_i$,$z$个$c_i$.这样，每个数组的大小都是$x+y+z$. **你希望从每个数组里选择1个整数，使得它们的xor(按位异或)值恰好为$t$.** 对于区间$[0,2^k-1]$内的每个数字$t$,输出满足上面的条件的方案数 模 $998244353$ 输入: 第一行读入$n,k$,第二行读入$x,y,z$,接下来读入$n$行。第$i$行读入$a_i$,$b_i$,$c_i$。 输出： 一行$2^k$个整数,用空格分隔。第$i$个数字是从每个数组里选一个整数使它们的xor值等于$t=i-1$的方案数模$998244353$ 贡献者:SIGSEGV

题目描述

You have received your birthday gifts — $ n $ triples of integers! The $ i $ -th of them is $ \lbrace a_{i}, b_{i}, c_{i} \rbrace $ . All numbers are greater than or equal to $ 0 $ , and strictly smaller than $ 2^{k} $ , where $ k $ is a fixed integer. One day, you felt tired playing with triples. So you came up with three new integers $ x $ , $ y $ , $ z $ , and then formed $ n $ arrays. The $ i $ -th array consists of $ a_i $ repeated $ x $ times, $ b_i $ repeated $ y $ times and $ c_i $ repeated $ z $ times. Thus, each array has length $ (x + y + z) $ . You want to choose exactly one integer from each array such that the XOR (bitwise exclusive or) of them is equal to $ t $ . Output the number of ways to choose the numbers for each $ t $ between $ 0 $ and $ 2^{k} - 1 $ , inclusive, modulo $ 998244353 $ .

输入输出格式

输入格式

The first line contains two integers $ n $ and $ k $ ( $ 1 \leq n \leq 10^{5} $ , $ 1 \leq k \leq 17 $ ) — the number of arrays and the binary length of all numbers. The second line contains three integers $ x $ , $ y $ , $ z $ ( $ 0 \leq x,y,z \leq 10^{9} $ ) — the integers you chose. Then $ n $ lines follow. The $ i $ -th of them contains three integers $ a_{i} $ , $ b_{i} $ and $ c_{i} $ ( $ 0 \leq a_{i} , b_{i} , c_{i} \leq 2^{k} - 1 $ ) — the integers forming the $ i $ -th array.

输出格式

Print a single line containing $ 2^{k} $ integers. The $ i $ -th of them should be the number of ways to choose exactly one integer from each array so that their XOR is equal to $ t = i-1 $ modulo $ 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 

说明

In the first example, the array we formed is $ (1, 0, 0, 1, 1, 1) $ , we have two choices to get $ 0 $ as the XOR and four choices to get $ 1 $ . In the second example, two arrays are $ (0, 1, 1, 2) $ and $ (1, 2, 2, 3) $ . There are sixteen $ (4 \cdot 4) $ choices in total, $ 4 $ of them ( $ 1 \oplus 1 $ and $ 2 \oplus 2 $ , two options for each) give $ 0 $ , $ 2 $ of them ( $ 0 \oplus 1 $ and $ 2 \oplus 3 $ ) give $ 1 $ , $ 4 $ of them ( $ 0 \oplus 2 $ and $ 1 \oplus 3 $ , two options for each) give $ 2 $ , and finally $ 6 $ of them ( $ 0 \oplus 3 $ , $ 2 \oplus 1 $ and four options for $ 1 \oplus 2 $ ) give $ 3 $ .

题意翻译

你的生日礼物是$n$个整数三元组。第$i$个三元组是$\{a_i,b_i,c_i\}$,所有数字$j$都满足$0\le j<2^k$,$k$是一个固定的数字，将由题目输入。 一天，你玩三元组玩腻了，所以你有了3个新的整数$x,y,z$,然后填充了$n$个数组。第$i$个数组有$x$个$a_i$,$y$个$b_i$,$z$个$c_i$.这样，每个数组的大小都是$x+y+z$. **你希望从每个数组里选择1个整数，使得它们的xor(按位异或)值恰好为$t$.** 对于区间$[0,2^k-1]$内的每个数字$t$,输出满足上面的条件的方案数 模 $998244353$ 输入: 第一行读入$n,k$,第二行读入$x,y,z$,接下来读入$n$行。第$i$行读入$a_i$,$b_i$,$c_i$。 输出： 一行$2^k$个整数,用空格分隔。第$i$个数字是从每个数组里选一个整数使它们的xor值等于$t=i-1$的方案数模$998244353$ 贡献者:SIGSEGV