문제 99
XOR 합성곱
길이가 $2^K$인 두 정수 수열 $A_0, A_1, \cdots, A_{2^K-1}$과 $B_0, B_1, \cdots, B_{2^K-1}$이 주어진다.
각 정수 $x$ $(0 \le x < 2^K)$에 대해 다음과 같이 정의한다.
$$ C_x = \sum_{i=0}^{2^K-1} A_i B_{i \oplus x}. $$
여기서 $\oplus$는 비트별 XOR 연산이다. 수열 $C$를 구해보자.
입력
첫 번째 줄에 정수 $K$가 주어진다. $(0 \le K \le 20)$
두 번째 줄에 $2^K$개의 정수 $A_0, A_1, \cdots, A_{2^K-1}$이 공백으로 구분되어 주어진다. $(-10^6 \le A_i \le 10^6)$
세 번째 줄에 $2^K$개의 정수 $B_0, B_1, \cdots, B_{2^K-1}$이 공백으로 구분되어 주어진다. $(-10^6 \le B_i \le 10^6)$
출력
$C_0, C_1, \cdots, C_{2^K-1}$을 공백으로 구분하여 출력한다.
예제 입력 1
0 1 -2
예제 출력 1
-2
예제 입력 2
2 1 2 3 4 4 3 2 1
예제 출력 2
20 22 28 30