Tổng trên tập con (SOS DP)

Cho số nguyên $N$ và mảng $f[0],f[1],\dots ,f[2^N-1]$ gồm $2^N$ số nguyên.

Với mỗi mask $m$ thuộc $\{0,1,\dots ,2^N-1\}$, định nghĩa

$$g[m]=\sum _{s\subseteq m}f[s],$$

trong đó $s\subseteq m$ có nghĩa là $s<mrow><mi>\&</mi></mrow>m=s$ (mọi bit của $s$ đều nằm trong $m$). Cả $m$ và $0$ đều là tập con của $m$.

Hãy in ra dãy $g[0],g[1],\dots ,g[2^N-1]$.

Dữ liệu vào

• Dòng 1: số nguyên $N$.
• Dòng 2: $2^N$ số nguyên $f[0],f[1],\dots ,f[2^N-1]$ cách nhau bởi dấu cách.

Dữ liệu ra

• Gồm $2^N$ dòng. Dòng thứ $m+1$ (tính từ $1$) chứa giá trị $g[m]$.

Ràng buộc

• $1\le N\le 20$ (do đó $2^N\le 1048576$).
• $-{10}^9\le f[m]\le {10}^9$.
• $|g[m]|\le 2^{20}·{10}^9\approx {10}^{15}$, vừa khít kiểu nguyên 64-bit có dấu.

Ví dụ

Ghi chú

Cách làm ngây thơ duyệt mọi cặp $(m,s)$ với $s\subseteq m$ tốn $O(3^N)$ ($\approx 3.5·{10}^9$ khi $N=20$) và không kịp thời gian. Bài toán có một cách giải kinh điển chạy trong $O(N·2^N)$.