Little C Loves 3 III
Contest: Codeforces Round 511 (Div. 1)
Difficulty rating: 3200
Tags: bitmasks, dp, math

Little C loves number «3» very much. He loves all things about it.

Now he is interested in the following problem:

There are two arrays of $$$2^n$$$ intergers $$$a_0,a_1,...,a_{2^n-1}$$$ and $$$b_0,b_1,...,b_{2^n-1}$$$.

The task is for each $$$i (0 \leq i \leq 2^n-1)$$$, to calculate $$$c_i=\sum a_j \cdot b_k$$$ ($$$j|k=i$$$ and $$$j\&k=0$$$, where "$$$|$$$" denotes bitwise or operation and "$$$\&$$$" denotes bitwise and operation).

It's amazing that it can be proved that there are exactly $$$3^n$$$ triples $$$(i,j,k)$$$, such that $$$j|k=i$$$, $$$j\&k=0$$$ and $$$0 \leq i,j,k \leq 2^n-1$$$. So Little C wants to solve this excellent problem (because it's well related to $$$3$$$) excellently.

Help him calculate all $$$c_i$$$. Little C loves $$$3$$$ very much, so he only want to know each $$$c_i \& 3$$$.

Input format:
The first line contains one integer $$$n (0 \leq n \leq 21)$$$.

The second line contains $$$2^n$$$ integers in $$$[0,3]$$$ without spaces — the $$$i$$$-th of them is $$$a_{i-1}$$$.

The third line contains $$$2^n$$$ integers in $$$[0,3]$$$ without spaces — the $$$i$$$-th of them is $$$b_{i-1}$$$.

Output format:
Print one line contains $$$2^n$$$ integers in $$$[0,3]$$$ without spaces — the $$$i$$$-th of them is $$$c_{i-1}\&3$$$. (It's obvious that $$$c_{i}\&3$$$ is in $$$[0,3]$$$).

Constraints:
Time limit: 1.0 s
Memory limit: 64.0 MB

Example input:
1
11
11

Example output:
12

Example input:
2
0123
3210

Example output:
0322

Editorial:
If we only need to calculate $$$c_i=\sum a_j \cdot b_k$$$ ($$$j|k=i$$$), we can do these:
1. Let $$$A_i=\sum a_j, B_i=\sum b_j$$$ ($$$j|i=i$$$).
2. Let $$$C_i=A_i \cdot Bi$$$, it can be found that $$$C_i=\sum c_j$$$ ($$$j|i=i$$$).
3. So $$$c_i=C_i-\sum c_j$$$ ($$$j|i=i$$$ and $$$j \neq i$$$).
To calculate $$$A_i$$$ fast ($$$B_i$$$ is the same), let $$$f(x,i)$$$ be the sum of $$$a_j$$$ which $$$j|i=i$$$ and the lower $$$x$$$ binary bits of $$$j$$$ is equal to $$$i$$$'s.
So $$$f(n,i)=a_i$$$, $$$f(x-1,i)=f(x,i)$$$ if $$$i|2^x=0$$$ , $$$f(x-1,i)=f(x,i)+f(x,i-2^x)$$$ if $$$i|2^x=2^x$$$, and $$$A_i=f(0,i)$$$.
We can calculate all $$$A_i$$$ and $$$B_i$$$ in $$$O(n \cdot 2^n)$$$ time.
Geting $$$c_i$$$ from $$$C_i$$$ is the inversion of getting $$$A_i$$$ from $$$a_i$$$. So we can use $$$f(x,i)$$$ once again. $$$f(x,i)=f(x-1,i)$$$ if $$$i|2^x=0$$$, $$$f(x,i)=f(x-1,i)-f(x-1,i-2^x)$$$ if $$$i|2^x=2^x$$$. So we can get all $$$c_i$$$ in $$$O(n \cdot 2^n)$$$ total time.
But in this problem we need to calculate $$$c_i=\sum a_j \cdot b_k$$$ ($$$j|k=i$$$ and $$$j\&k=0$$$).
In fact, there is a well-known algorithm for this problem.
The main idea of this algorithm is consider the number of "$$$1$$$" binary bits.
First, let $$$BC(x)$$$ be the number of "$$$1$$$" binary bits in $$$x$$$.
Let $$$A(x,i)=\sum a_j, B(x,i)=\sum b_j$$$ ($$$j|i=i$$$ and $$$BC(j)=x$$$).
Then we calculate $$$C(x,i)=\sum A(y,i) \cdot B(z,i)$$$ ($$$y+z=x$$$), and $$$c(x,i)=C(x,i)-\sum c(x,j)$$$ ($$$j|i=i$$$ and $$$j \neq i$$$).
So $$$c(x,i)=\sum a_j \cdot b_k$$$ ($$$j|k=i$$$ and $$$BC(j)+BC(k)=x$$$).
Finally $$$c_i$$$ we need to calculate is equal to $$$c(BC(i),i)$$$, because if $$$j|k=i$$$ and $$$BC(j)+BC(k)=BC(i)$$$, $$$j\&k$$$ must be $$$0$$$.
This algorithm cost $$$O(n^2 \cdot 2^n)$$$ time. Unfortunately, it may be too slow in this problem.
In this problem, we only need to calculate $$$c_i\&3$$$, equal to $$$c_i$$$ module $$$4$$$.
In fact, when the answer is module $$$p$$$, an arbitrarily integer, my solution works.
Let $$$A_i=\sum a_j \cdot p^{BC(j)} (j|i=i)$$$.
Then we calculate $$$F_i=A_i \cdot B_i$$$, and $$$f_i=F_i-\sum f_j$$$ ($$$j|i=i$$$ and $$$j \neq i$$$).
So $$$f_i=\sum a_j \cdot b_k \cdot p^{BC(j)+BC(k)}$$$ ($$$j|k=i$$$).
If $$$j|k=i$$$, $$$BC(j)+BC(k) \geq BC(i)$$$. If $$$j|k=i$$$ and $$$j\&k=0$$$, $$$BC(j)+BC(k)=BC(i)$$$.
We find that $$$c_i \equiv \frac{f_i}{p^{BC(i)}} (module\ p)$$$, because if $$$BC(j)+BC(k)>BC(i)$$$, $$$a_j \cdot b_k \cdot p^{BC(j)+BC(k)-BC(i)}$$$ can be divided by $$$p$$$.
So the total time is $$$O(n \cdot 2^n)$$$.
A remainder problem is it can not be module $$$p$$$ when calculating in this algorithm, so the number may be very large.
Fortunately, in this problem, $$$p$$$ is only $$$4$$$. We can use 128-bit integers or merge two 64-bit integers into one number when calculating.
But in fact, we only care $$$\frac{f_i}{p^{BC(i)}}$$$ module $$$p$$$, so we can let all number be module $$$p^{n+1}$$$. Single 64-bit integer is enough.