原问题可以写成 2d 个形式幂级数多项式的乘积。考虑进行 FWT/IFWT， 则问题可以转化成： 求 ∑2 i=0 d−1 b′ i ∏2 j=0 d−1(1 + (−1)popcount(i & j)ajx)，其中 b′ 是数组 b 经过 IFWT 的结果。 考虑对每个 i 计算 Qi = ∏2 j=0 d−1(1 + (−1)popcount(i & j)ajx)。 记多项式序列 Pi(0 ≤ i < 2d) 初始时满足 Pi = 1 + aix。则可以用类似 FWT 的方法计算 Q： 具体地，枚举二进制位 i，不妨取一个第 i 位为 0 的下标 j 和 k = j + 2i， 并令 (Pj(x); Pk(x)) = (Pj(x)Pk(x); Pj(x)Pk(−x))。则过程结束后 P 即为所求的 Q。 由于任意模数卷积很慢，而最终只要求一个多项式，可以考虑插值。具体 地，使用 −2d−1 ∼ 2d−1 的点值并用上述方法同时计算答案在 x 和 −x 处的点值 即可。 总复杂度 O(d4d)。