Subset Convolution

AC一覧

Problem Statement (Japanese) / 問題文 (日本語)

長さ $2^N$ の整数列 $a_0, a_1, \dots, a_{2^N - 1}$, $b_0, b_1, \dots, b_{2^N - 1}$ が与えられます。以下の数列 $c_0, c_1, \dots, c_{2^N - 1}$ を $\bmod 998{,}244{,}353$ で計算してください。

$c_k = \sum_{i, j, i \& j = 0, i | j = k} a_i b_j$

ただし $i \& j, i | j$ はそれぞれbitwise-AND, bitwise-ORとします

Constraints / 制約

Input / 入力

$N$
$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}$

Sample / サンプル

# 1

3
1 2 3 4 5 6 7 8
9 10 11 12 13 14 15 16
9 28 38 100 58 144 172 408

Forum


Timelimit: 10 secs