Fast multiplication with a full binary $n \times 2^n$ matrix
Suppose that $A$ were a $1 \times n$ matrix, let $X_n$ denote your matrix for a given value of $n$, and let $A_{&lt;n}$ consist of all but the last entry $A_n$ of $A$. Then up to rearrangement,
$$
AX_n = \begin{bmatrix} A_{&lt;n} X_{n-1} &amp; A_{&lt;n} X_{n-1} + A_n \end{bmatrix},
$$
where $+A_n$ means adding $A_n$ to all entries. The running time of this procedure satisfies the recurrence
$$
T(n) = T(n-1) + O(2^{n-1}),
$$
whose solution is $T(n) = O(2^n)$, which is linear in the size of the output. This should be compared to the trivial $O(n2^n)$ solution.

You can save a factor of $n$ in your case in the same way. The resulting algorithm is asymptotically optimal.