博客园 我的博客 快速沃尔什变换解决的卷积问题 快速沃尔什变换（FWT）是解决这样一类卷积问题： \[c_i=\sum_{i=j\odot k}a_jb_k \]其中，\(\odot\) 是位运算的一种。举个例子，给定数列 \(a,b\)，求： \[c_i=\sum_{j\oplus k=i} a_
本文中使用 \(\cap\) 表示按位与，用 \(\cup\) 表示按位或 Part 1. 与/或 卷积 First. 问题引入 给定长度为 \(2^n\) 的数列 \(A,B\)，求 \(C_i = \sum_{j \cup k = i} A_j \times B_k\) 显然有 \(O(4^n)
