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

1. 概要 本記事では，部分集合・上位集合関係に関するゼータ変換，メビウス変換について解説します．ゼータ変換・メビウス変換はより一般に順序集合に対して定義されるものですが，本記事で扱うのはその特殊ケースということになります． 2. 前提知識 $\lbra…