CF1119H Triple

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 $ .

N/A

N/A

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 $ .