atcoder https://blog.hatena.ne.jp/atcoder/ AtCoderInfo https://info.atcoder.jp/ 集合関数 XOR XOR 畳み込み Walsh-Hadamard 変換 環 1. 概要 本記事では長さ $2 ^ N$ の列の XOR 畳み込みを求める問題を扱います． この問題は，整数列や実数列を対象とするような通常の状況では，Walsh-Hadamard 変換を用いて $\mathrm{O}(N\cdot 2 ^ N)$ 時間で求めることができます． Walsh-Hadamard 変換はその定義の定数倍にいくつかの流儀がありますが，いずれにせよこの計算方法には，数を $2$ やその累乗で割るという操作が含まれます．一方で，XOR 畳み込み自体は環演算のみ（つまり加算・減算・乗算のみ）で定義されるため，環演算のみを用いるアルゴリズムはないのかを考えるのも自然な問題で… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Finfo.atcoder.jp%2Fentry%2Falgorithm_lectures%2Fdivision_free_xor_convolution" title="XOR 畳み込み（除算なし） - AtCoderInfo" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://cdn.user.blog.st-hatena.com/default_entry_og_image/158934417/1702097020779738 Hatena Blog https://hatena.blog 2026-04-10 14:16:21 rich https://info.atcoder.jp/entry/algorithm_lectures/division_free_xor_convolution 1.0 100%