Subtask 1:

Ta chỉ cần làm đúng như những gì đề bài yêu cầu là được. Độ phức tạp thuật toán: $O(4^n)$.

Subtask 2:

Ta biểu diễn hai mảng dưới dạng hai đa thức:
• $X=A[0]+A[1]\ast x+A[2]\ast x^2+...+A[2^n-1]\ast x^{2^n-1}$.
• $Y=B[0]+B[1]\ast x+B[2]\ast x^2+...+B[2^n-1]\ast x^{2^n-1}$.

Khi đó, ta dễ thấy đa thức biểu diễn mảng $C$: $Z=C[0]+C[1]\ast x+C[2]\ast x^2+...+C[2^n-1]\ast x^{2^n-1}$ về cơ bản là nhân hai đa thức $X$ và $Y$, nhưng thay vì ta cộng số mũ khi nhân hai đơn thức bất kì, ta sẽ lấy phép OR số mũ. Như vậy, bài toán trở về nhân nhanh hai đa thức. Có nhiều thuật toán có thể thực hiện được điều này, như thuật toán Karatsuba với độ phức tạp $O(3^n)$, nhưng phổ thông nhất và nhanh nhất vẫn là thuật toán FFT (Fast Fourier Transform), với độ phức tạp $O(2^n\ast n)$.

Edit: Thuật toán Karatsuba với toán tử OR có thể nhân hai đa thức trong $O(2^n\ast n)$, cơ mà với các toán tử khác như XOR, phép cộng, ... thì vẫn là $O(3^n)$.