XOR 畳み込み（除算なし）

集合関数 XOR XOR 畳み込み Walsh-Hadamard 変換 環

1. 概要

本記事では長さ $2 ^ N$ の列の XOR 畳み込みを求める問題を扱います．

この問題は，整数列や実数列を対象とするような通常の状況では，Walsh-Hadamard 変換を用いて $\mathrm{O}(N\cdot 2 ^ N)$ 時間で求めることができます．

Walsh-Hadamard 変換はその定義の定数倍にいくつかの流儀がありますが，いずれにせよこの計算方法には，数を $2$ やその累乗で割るという操作が含まれます．一方で，XOR 畳み込み自体は環演算のみ（つまり加算・減算・乗算のみ）で定義されるため，環演算のみを用いるアルゴリズムはないのかを考えるのも自然な問題です．

本記事では，XOR 畳み込みを環演算のみで $\mathrm{O}(N ^ 2\cdot 2 ^ N)$ 時間で解く方法を解説します．なお，この問題は次のコンテストで出題されたものです．

XOR 畳み込みは古典的で有名な問題ですが，環演算のみのアルゴリズムという制約をつけるだけで，いまでも新しい見方や解法が現れるのが面白い点です．競技プログラミングで実用する機会はほとんどないと思いますが，ぜひ学んでみてください．

2. 前提知識

以下のアルゴリズムの理解を前提とします．

  • XOR 畳み込み（Walsh-Hadamard 変換を用いて $\mathrm{O}(N\cdot 2 ^ N)$ 時間で計算する方法）．
  • 部分集合畳み込み．

3. 問題設定

$R$ を環とします．特に，$R$ には加算・乗算が定義されており，次が仮定されます．

  • $R$ と加算の組は可換群である．
  • $R$ と乗算の組はモノイドである．
  • 分配法則が成り立つ．

詳しくは 代数構造用語集 【定義 13】 を参照してください．（なお学習時に強く意識する必要はないと思いますが，本記事のアルゴリズムにおいて乗算の可換性は不要です．） また計算量解析においては，$R$ の環演算等を $\mathrm{O}(1)$ として扱います．

環が抽象的だと感じる場合，ひとまず $R=\mathbb{Z}$（整数全体）として「除算をしないルールのもとで計算する」と思って読んでも問題ありません．

$N$ を非負整数とし，$\lbrace 0,1,\ldots,N-1\rbrace$ の部分集合を通常の方法で $0$ 以上 $2 ^ N - 1$ 以下の非負整数と対応させて扱います．$R$ の要素からなる長さ $2 ^ N$ の列全体を $R ^ {2 ^ N}$ と表記します．

本記事で扱うのは次の問題です．

【問題 1】
$A, B \in R ^ {2 ^ N}$ に対して，その XOR 畳み込みを求めてください．つまり， $$C_U = \sum_{S\oplus T = U}A_S B_T$$ により定まる $C\in R ^ {2 ^ N}$ を求めてください．

この問題は，$R$ が体であるなどの除算が可能な場合には Walsh-Hadamard 変換による解法が有名です．この解法には，$2$ あるいはその累乗による除算が登場するため，【問題 1】 には一般には適用できません．そのような場合が本記事の主要なテーマです．

ただし，本記事で解説する解法が必須となる場面はかなり限られます．（実際の出題例でも Walsh-Hadamard 変換による解法を阻止するために，かなり特殊な出題形式がとられています．）

例えば競技プログラミングで最も基本的な環は $\mathbb{Z}$ あるいは $\mathbb{Z}/m\mathbb{Z}$ だと思います．これらの場合を考えてみましょう．

$\mathbb{Z}$ の場合には，$2 ^ N$ が乗法逆元を持たないといっても「$2 ^ N x$ が与えられたときに $x$ を求める」ことはできるので，Walsh-Hadamard 変換による解法が適用できます．

$\mathbb{Z}/m\mathbb{Z}$ の場合には，入力を $0$ 以上 $m-1$ 以下の整数として扱い，$\mathbb{Z}$ で XOR 畳み込みをした後で答の $m$ による剰余をとるという手順をとることができます．$m$ が $30$ bit 程度であれば少し大きな整数型を使う，あるいは数個の素数を法として計算したあと中国剰余定理で復元することなどでこれを行うことができます．

4. 解法

4.1. 多項式による言い換え

$R$ を係数環とし，$x_0,x_1,\ldots,x_{N-1}$ を不定元とする多項式を考えます．集合 $S\subseteq \lbrace 0,1,\ldots,N-1\rbrace$ に対して，

$$x ^ S = \prod_{i\in S} x_i$$

と定義します．長さ $2 ^ N$ の配列 $A \in R ^ {2 ^ N}$ に対し，多項式 $\sum_{S} A_S x ^ S$ を対応させることで，【問題 1】 の入出力は $N$ 変数で各変数についての次数が $1$ 以下であるような多項式と考えることができます．$A$ に対応する多項式を $A(x)$ と書くことにします（$B(x), C(x)$ なども同様とします）．

$C$ が $A,B$ の XOR 畳み込みであるとするとき，次が成り立ちます：

$$A(x)B(x)\bmod (x_0 ^ 2-1,\ldots,x_{N-1} ^ 2-1) = C(x). $$

つまり，積 $A(x)B(x)$ を求めたあと，各 $x_i ^ 2$ を $1$ に置き換えるという操作をすべての $i$ について行うことで $C(x)$ が得られます．このことは XOR の定義から直接分かります．

4.2. 変数変換

$y_i = x_i + 1$ （同じことですが，$x_i = y_i - 1$）とします．

$x_i ^ 2-1=y_i ^ 2-2y_i$ なので，本記事の問題を解くためには

  1. $A(x)=A_1(y)$ であるような $A_1\in R ^ {2 ^ N}$ を求める．
  2. $B(x)=B_1(y)$ であるような $B_1\in R ^ {2 ^ N}$ を求める．
  3. $C_1(y)= A_1(y)B_1(y) \bmod {(y _ 0 ^ 2-2 y _ 0,\ldots,y _ {N - 1} ^ 2 - 2 y _ {N - 1})}$ であるような $C_1\in R ^ {2 ^ N}$ を求める．
  4. $C_1(y)=C(x)$ であるような $C\in R ^ {2 ^ N}$ を求める．

このうち，1, 2, 4 は易しいです．$i=0,1,\ldots,N-1$ の順に，$x_i$ を $y_i$ に変換する（あるいはその逆）ということを行っていけばよく，$\mathrm{O}(N\cdot 2 ^ N)$ 時間で計算できます．（同じことですが，$2\times 2$ 行列 $N$ 個のクロネッカー積をかける操作なので $\mathrm{O}(N\cdot 2 ^ N)$ 時間で計算できると考えてもよいでしょう．）

なお，1, 2 は上位集合関係に関するメビウス変換，4 は上位集合関係に関するゼータ変換です．

残りは 3，つまり多項式の積を $\bmod (y _ 0 ^ 2-2 y _ 0,\ldots,y _ {N - 1} ^ 2 - 2 y _ {N - 1})$ で求める部分です．

4.3. $\pmod{y_i ^ 2-2y_i}$ での多項式積

解くべき問題は次の通りです．

【問題 2】
$A, B \in R ^ {2 ^ N}$ に対して， $$C_U = \sum_{S\cup T = U}A_S B_T\cdot 2 ^ {|S|+|T|-|U|}$$ により定まる $C\in R ^ {2 ^ N}$ を求めてください．ただし，集合 $S$ の要素数を $|S|$ と表します．

係数 $2 ^ {|S|+|T|-|U|}$ がなくて，単に $S\cup T = U$ であるような組 $(S,T)$ について $A_SB_T$ の和をとるだけであれば，OR 畳み込みとして知られる問題なので，部分集合関係に関するゼータ変換・メビウス変換により計算できます．言い換えれば，本問題では「$|S|+|T|$ の情報も上手く残しながら OR 畳み込みのようなことを行う」必要があります．

この状況は，部分集合畳み込みと似ています．

部分集合畳み込みの場合
$A, B\in R ^ {2 ^ N}$ の部分集合畳み込みは，

$$ C_U=\sum_{ \substack{ S\cup T=U, \\ |S|+|T|=|U| } } A_S B_T $$

と表すことができます．したがって部分集合畳み込みも，「$|S|+|T|$ の情報も上手く残しながら OR 畳み込みのようなことを行う」問題だと言えます．

この観点から本節の問題は部分集合畳み込みと非常に似ています．実際，部分集合畳み込みを理解している方にとっては以下のアルゴリズムは容易に導出できるでしょう．

このことは，ランク付きの OR 畳み込みを求めることで解決できます．

$A, B$ は $R$ の要素の列ですが，これに次のように集合の大きさの情報を持たせて，多項式の列 $\hat{A}, \hat{B}$ を作ります．つまり，次のようにします．

$$\hat{A} _ S = A _ S t ^ {|S|}, \qquad \hat{B} _ T = B _ T t ^ {|T|}.$$

そして，$\hat{A}, \hat{B}$ の OR 畳み込みを $\hat{C}$ とします．つまり：

$$\hat{C} _ U = \sum _ {S\cup T=U} \hat{A} _ S \hat{B} _ T.$$

とします．すべての $U$ に対する $\hat{C}_U$ は，ランク付きのゼータ変換・メビウス変換を用いて $\mathrm{O}(N ^ 2\cdot 2 ^ N)$ 時間で計算できます．この計算は部分集合畳み込みと完全に同一です．

以上によりすべての $U$ に対して

$$\hat{C} _ U = \sum_{S\cup T=U} \hat{A} _ S \hat{B} _ T = \sum _ {S \cup T=U} A _ S B _ T \cdot t ^ {|S|+|T|}$$

を求めることができました．ここから

$$C_U=\sum_{S\cup T=U} A_SB_T\cdot 2 ^ {|S|+|T|-|U|}$$

を求めるのは容易です．$2N$ 次以下の多項式 $f(t)$ に対して，$\sum_{u\leq i}f_i\cdot 2 ^ {i-u}$ を求めるというタイプの計算をするだけです．

以上により，【問題 1】 を $\mathrm{O}(N ^ 2\cdot 2 ^ N)$ 時間で解くことができます．

4.4. 実装例

Library Checker Bitwise Xor Convolution への提出です．

5. 関連問題

  1. https://judge.yosupo.jp/problem/bitwise_xor_convolution
  2. https://uoj.ac/contest/103/problem/1015
  3. https://yukicoder.me/problems/no/1901

6. まとめ

本記事では，環演算のみで（除算なしで）長さ $2 ^ N$ の列の XOR 畳み込みを $\mathrm{O}(N ^ 2\cdot 2 ^ N)$ 時間で求める方法を解説しました．

7. 参考文献

  1. Flamire．UOJ Long Round #3 题解．UOJ Blogs．https://flamire.blog.uoj.ac/blog/9767．（閲覧日: 2026-03-31）．
  2. Andreas Björklund, Thore Husfeldt, Petteri Kaski, Mikko Koivisto．Fourier meets Möbius: fast subset convolution．Proceedings of the 39th Annual ACM Symposium on Theory of Computing (STOC)．pp. 67–74．2007．DOI: 10.1145/1250790.1250801．https://doi.org/10.1145/1250790.1250801．

トップページ：AtCoder Algorithm Lectures