XOR 畳み込み（除算なし）

1. 概要 本記事では長さ $2 ^ N$ の列の XOR 畳み込みを求める問題を扱います． この問題は，整数列や実数列を対象とするような通常の状況では，Walsh-Hadamard 変換を用いて $\mathrm{O}(N\cdot 2 ^ N)$ 時間で求めることができます． Walsh-Hadamard 変換…