P6097 【模板】子集卷积

$\color{deeppink}link$

长度为 $2^n$ 的序列 $a,b$，计算 $c$，其中

$c_k=\sum_{\begin{aligned}i~\vert~j=k\\i~\&~j=0\end{aligned}}a_ib_j$

第一个条件用 $\texttt{FWT}$ 解决，但是第二个条件就有点难办了。

注意到只有 $\vert i\vert+\vert j\vert=i~\texttt{or} ~j$ 时 $i~\&~j=0$。

那么可以考虑占掉 $0$ 的位置。

令 $F_{i,j}=\left\{ \begin{aligned} & a_j&&|j|=i\\ & 0 &&\texttt{otherwise}\\ \end{aligned} \right.$，$G_{i,j}$ 同理。

令 $H_i=\sum\limits_{j=0}^iF_j*G_{i-j}$。

如此，$F*G$ 所得到的 $H$ 中，每一个 $H_{|S|,S}$ 都是正确的，因为 $|S|$ 相当于两个数拼在一起的长度，$S$ 就是他们的并。

最后的答案就是 $ans_i=H_{|i|,i}$。时间是 $O(n\log^2n)$ 的。