Subset Convolution

AC一覧

Problem Statement
問題文

Given size $2^N$ interger 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 998{,}244{,}353$.

$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.

長さ $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

Before submitting, please confirm terms and conditions