【题目描述】
给定长度为 2N 的整数序列 a0,a1,…,a2N−1 和 b0,b1,…,b2N−1。按如下方式计算整数序列 c0,c1,…,c2N−1,并输出它 mod998244353 的结果。
ck=∑i,j,i⊕j=kaibj
其中 i⊕j 表示按位异或。
【输入】
文本
$N$
$a_0$ $a_1$ ... $a_{2^N - 1}$
$b_0$ $b_1$ ... $b_{2^N - 1}$
【输出】
文本
$c_0$ $c_1$ ... $c_{2^N - 1}$
【输入样例】
文本
3
1 2 3 4 5 6 7 8
9 10 11 12 13 14 15 16
【输出样例】
文本
492 488 476 472 428 424 412 408
【数据范围】
- 0≤N≤20
- 0≤ai<998244353
- 0≤bi<998244353
【来源】
Library Checker(yosupo06) bitwise_xor_convolution