시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 30 | 15 | 14 | 66.667% |
Bob is interested in popcount and some strange transforms. Currently, he is attacking the following problem:
There is an array of $2^n$ integers $a_0,a_1,a_2,\ldots,a_{2^n-1}$. The task is, for each $i$ ($0 \le i \le 2^n-1$), to calculate
$$b_i=\sum\limits_{j=0}^{2^n-1} (\operatorname{popcount}(i \, \operatorname{and} \, j) \bmod 2) \cdot a_j\text{,}$$
where "$\operatorname{popcount}(x)$" denotes the number of ones in the binary representation of $x$, and "$\operatorname{and}$" denotes the bitwise AND operation.
Although Bob is very smart, he still can't solve the problem fast. Can you help him calculate all $b_i$?
The first line contains a single integer $n$ ($1 \le n \le 20$).
The second line contains $2^n$ integers describing the array $a$ ($1 \le a_i \le 10^9$).
Print one line with $2^n$ integers, the $i$-th of them being the value $b_i$.
2 1 2 3 4
0 6 7 5