Skip to content →

Subset Convolutionのアルゴリズム

集合の畳み込み(Subset Convolution)
$$(f * g)(S) := \sum_{T \subseteq S} f(T) g(S \setminus T)$$ を全ての部分集合 \(S \subseteq [N]=\{1,\ldots,N\}\) に対して列挙するアルゴリズムを紹介します[1, 2]。

素朴な DP では

  vector dp(1 << n); // dp[S] := Σ[T⊆S] f(T)g(S\T)
  for (int s = 0; s < 1 << n; ++s) {
    for (int t = s; t >= 0; --t) {
      t &= s;
      dp[s] += f(t) * g(s ^ t);  
    }
  }

となり、\(O(3^n)\) ですが、 \(O(n^22^n)\) でできます。

\(F(x_1,\ldots,x_n)G(x_1,\ldots,x_n) \bmod (x_1^2,\ldots,x_n^2)\) を求める問題だと捉えれば、\(\mathbb{R}\) 係数や \(\mathbb{Z}/p\mathbb{Z}\) 係数(\(p\) : 素数)のときは FFT を使って \(O(n^2 2^n)\) を達成できます(多変数畳み込み(切り捨て))。しかし、環係数では逆元が存在しませんから、FFT できません。この記事ではより軽い、一般の環係数で \(O(n^2 2^n)\) を達成するアルゴリズムを扱います。

アルゴリズム[1]

元の個数を \(x\) のべき指数にした $$F(S)=f(S)x^{|S|}, G(S)=g(S)x^{|S|}$$ を定義します。また、条件を緩めた畳み込み
$$(F \star G)(S) := \sum_{U, V \subseteq S \\ U \cup V = S} F(U) G(V) $$を定義します。\(x\) の冪指数が \(U\) と \(V\) の(重複を込めた)元の個数を表しているので、求めたいのは$$(F \star G)(S) \bmod x^{|S|+1} = (f*g)(S)x^{|S|}$$ です。この式がアルゴリズムに適しているのは、元の個数のみを記憶して、どの元が \(U\) と \(V\) で重複したかを忘れている点です。情報を圧縮して持っているので、計算量削減が期待できます(同様のアイディアが使われたアルゴリズム:多変数畳み込み(切り捨て))。

ゼータ元 \(\zeta\) を右から掛けると、
\begin{align}((F \star G) * \zeta) (S) =& \sum_{T \subseteq S}\ \sum_{U, V \subseteq T \\ U \cup V = T} F(U) G(V) \\ =&\sum_{U \subseteq S} F(U) \sum_{V \subseteq S} G(V) \\
\\ =& (F * \zeta)(S) \cdot (G * \zeta)(S) \end{align}となります。\(F \star G\) のゼータ変換が、\(F\) と \(G\) のゼータ変換の積になりました! 右からメビウス元 \(\mu\) を掛けると逆変換になり、$$(F \star G) (S) = (((F * \zeta) (G * \zeta)) * \mu)(S)$$ を得ます。高々 \(n\) 次の多項式を値に取る関数 \(F, G\) の高速ゼータ変換、高速メビウス変換をすればよいので、計算量は \(O(2^nn^2)\) です。

このような、元の個数を持ったゼータ変換・メビウス変換を [1] では ranked zeta transform, ranked M¨obius transform と呼んでいます。

アルゴリズム[2]

[2]では(同じ式を)別の角度から見たアルゴリズムが設計されています。 \(S \subseteq [N-1]\) とします。\([N-1]\) の冪集合に定義域を制限した \(F_0 (S):= F|_{2^{[N-1]}}(S)\) と \({N}\) を加えた、\(F_1(S) := F|_{2^{[N-1]}}(S \cup \{N\})\) を定義します。\(G_0, G_1\) も同様に定義します。すると漸化式$$ (F \star G)(S \cup \{N\}) = ((F_0 + F_1) \star (G_0 + G_1))(S)-(F_0 \star G_0) (S) $$が成り立ちます。集合のサイズが1減少したかわりに、畳み込む関数の係数の次数が1つ増えました。つまり \(F \star G\) を列挙する問題は

  • \(F_0 \star G_0\) for all \(S \subseteq [N-1]\)
  • \((F_0+F_1) \star (G_0+G_1)-F_0 \star G_0 \) for all \(S \subseteq [N-1]\)

を列挙する部分問題に帰着できます。

部分問題への帰着を繰り返した時の計算量を求めましょう。係数が高々 \(k\) 次の関数の畳み込み (\(\star\)) を、\(n\) 元集合の全ての部分集合について列挙する計算量を \(T(n,k)\) とすると、\(T(n,k)=2T(n-1,k+1)+O(n)\) が成り立ちます。\(O(n)\) は多項式の引き算の計算量です。求めたいのは \(T(n,0)\) でした。漸化式を繰り返し適用して、\(T(n,0)=2^nT(0,n)+O(n^22^n)\) を得ます。\(T(n,0)\) は高々 \(n\) 次多項式の積の計算量ですから、 \(T(n,0)=O(n^22^n)\) です。

実装例 : 再帰, 非再帰

複数回の subset convolution

複数回の subset convolution は各点積で一度に計算してしまえます。つまり
$$(f_1*f_2*\cdots*f_m)(S) = \prod_{S=\bigsqcup U_i} f_i(U_i)$$とすると、
$$((F_1 \star F_2 \star \cdots \star F_m) * \zeta) (S) \\
=(F_1 * \zeta)(S) \cdot (F_2 * \zeta)(S) \cdot \cdots \cdot (F_m * \zeta)(S) $$となります。

証明:\(m=2\)の場合はすでに示しました。\(m=k-1\)で成立を仮定します。次のように \(m=k\) のとき、\(m=k-1\) に帰着できるので帰納法により証明終了。$$\begin{align}&((F_1 \star (F_2 \star F_3\star \cdots \star F_k)) * \zeta) (S)\\
=&(F_1 * \zeta)(S) \cdot ((F_2 \star F_3\star \cdots \star F_k) * \zeta)(S) \end{align}$$

各点積は、FFT のような多項式のアルゴリズムが使えます。また、subset の足し算・引き算は ranked Zeta transform した後も足し算・引き算です。従って、例えば subset の exp を求めたいとき、ranked Zeta transform してから、多項式の exp を求めるアルゴリズムが使えます。

参考文献

  1. Fourier Meets Mobius: Fast Subset Convolution
  2. 指数時間アルゴリズム入門
  3. Library Checker : Subset Convolution

Published in データ構造

Comments

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です

CAPTCHA