9027: [yosupo] Set Power Series - Subset Convolution
[Creator : ]
Description
Given size $2^N$ integer sequences $a_0, a_1, \dots, a_{2^N - 1}$ and $b_0, b_1, \dots, b_{2^N - 1}$. Calculate an integer sequence $c_0, c_1, \dots, c_{2^N - 1}$ as follows and print it $\bmod 998244353$.
$c_k = \sum_{i, j, i \& j = 0, i | j = k} a_i b_j$
We note that $i \& j, i | j$ mean bitwise-AND, bitwise-OR.
$c_k = \sum_{i, j, i \& j = 0, i | j = k} a_i b_j$
We note that $i \& j, i | j$ mean bitwise-AND, bitwise-OR.
Input
$N$
$a_0$ $a_1$ ... $a_{2^N - 1}$
$b_0$ $b_1$ ... $b_{2^N - 1}$
$a_0$ $a_1$ ... $a_{2^N - 1}$
$b_0$ $b_1$ ... $b_{2^N - 1}$
Output
$c_0$ $c_1$ ... $c_{2^N - 1}$
Constraints
$0 \leq N \leq 20$
$0 \leq a_i < 998244353$
$0 \leq b_i < 998244353$
$0 \leq a_i < 998244353$
$0 \leq b_i < 998244353$
Sample 1 Input
3
1 2 3 4 5 6 7 8
9 10 11 12 13 14 15 16
Sample 1 Output
9 28 38 100 58 144 172 408