3431 . [模板題] Bitwise Xor Convolution
TopCoder
Tags
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 \oplus j = k} a_ i b_ j$
We note that $i \oplus j$ means bitwise-XOR.
Input Format
$N$
$a_ 0$ $a_ 1$ ... $a_ {2^ N - 1}$
$b_ 0$ $b_ 1$ ... $b_ {2^ N - 1}$
Output Format
$c_ 0$ $c_ 1$ ... $c_ {2^ N - 1}$
Sample Input 1
3 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Sample Output 1
492 488 476 472 428 424 412 408
Hints
- $0 \leq N \leq 20$
- $0 \leq a_ i < 998244353$
- $0 \leq b_ i < 998244353$
Problem Source
Subtasks
| No. | Testdata Range | Score |
|---|