【题目描述】
给定大小为 2N 的整数序列 a0,a1,…,a2N−1 与 b0,b1,…,b2N−1。按如下方式计算出整数序列 c0,c1,…,c2N−1,并将其对 998244353 取模后输出。
ck=i,j,i&j=k∑aibj其中 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
【输出样例】
文本
957 412 515 208 751 292 337 128
【数据范围】
- 0≤N≤20
- 0≤ai<998244353
- 0≤bi<998244353
【来源】
Library Checker(yosupo06) bitwise_and_convolution