Subset Convolutionのアルゴリズム

集合の畳み込み（Subset Convolution）
$$\sum_{T \subseteq S} f(T) g(S \setminus T)$$ を全ての部分集合 $S \subseteq [n]=\{1,\ldots,n\}$ に対して列挙するアルゴリズムを紹介します[1, 2]。素朴な DP では　$O(3^n)$ ですが、 $O(n^22^n)$ にできます。

$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, 2]。

1 結びのゼータ変換・メビウス変換
2 ランク付きゼータ・メビウス変換
3 練習問題
4 参考文献

結びのゼータ変換・メビウス変換

半順序集合は、任意の単項順序イデアルが有限であるとき、単項順序イデアルの和（ゼータ変換）の逆操作（メビウス変換）が定義できます。それは、メビウス関数を $\mu$、$f$ のゼータ変換を $f\zeta $ と書くと
\begin{align}
f\zeta (x) &= \sum_{y \leq x} f(y) \\
f(x) &= \sum_{y \leq x} \mu(y, x)f\zeta (y)
\end{align}
の形で書けます。同じ半順序集合上の関数 $f_1, f_2$ で結びを取った $f(x) = \sum_{x_1 \lor x_2 = x} f_1(x_1) f_2(x_2)$ のゼータ変換は

\begin{align}
f\zeta(x) &= \sum_{y \leq x} f(y) \\
&= \sum_{x_1 \lor x_2 \leq x} f_1(x_1)f_2(x_2) \\
&= \sum_{x_1 \leq x} f_1(x_1) \sum_{x_2 \leq x} f_2(x_2)\\
&= f_1\zeta(x) f_2\zeta(x)
\end{align}
となり、$f_1, f_2$ のゼータ変換の積に分解できます。従って、

$f_1, f_2$ のゼータ変換 $ f_1\zeta, f_2\zeta$ を求める。
$ f_1\zeta, f_2\zeta$ の各点積を計算する。これが $ f\zeta$ に等しい。
$ f\zeta$ をメビウス変換する。

というアルゴリズムで $f$ が求まります。各点積を $*$ で書くことにすると、$f = ( f_1 \zeta * f_2\zeta)\zeta^{-1}$ となります。本記事のアルゴリズムが適用できる半順序集合には次のようなものがあります。

$N$ の約数について、$i \leq j \Leftrightarrow i \mid j$ という順序を定めた半順序集合 $D_N$ 上では $f(k)=\sum_{\mathrm{lcm}(i, j) = k} f_1(i) f_2(j)$ となります。
$\{1, 2, \ldots, N\}$ の部分集合について、$S \leq T \Leftrightarrow S \subseteq T$ という順序を定めた半順序集合 $B_N$ 上では $f(k)=\sum_{i \cap j = k} f_1(i) f_2(j)$ となります。
$\mathbb{F}_q$ 係数 $N$ 次元線形空間の部分空間について、$S \leq T \Leftrightarrow S \subseteq T$ という順序を定めた半順序集合 $V_n(q)$ 上では $f(k)=\sum_{i \cap j = k} f_1(i) f_2(j)$ となります。

ランク付きゼータ・メビウス変換

$B_n$ において、集合 $x$ のサイズ $\rho(x)$ を不定元 $t$ のべき指数に乗せた
\begin{align}
f(x) &= \sum_{x_1 \lor x_2 = x} f_1(x_1) x_1^{\rho(x_1)} f_2(x_2)x_1^{\rho(x_2)} \\
&= \sum_{k} t^{k} \sum_{x_1 \lor x_2 = x,\\ k = \rho(x_1)+\rho(x_2)} f_1(x_1) f_2(x_2)
\end{align}
を求めることができれば、$[t^{\rho(x)}]f(x)$ が subset convolution になっています。これは、$f_1(x) t^{\rho(x)}, f_2(x)t^{\rho(x)}$ をそれぞれゼータ変換して各点積を取ってからメビウス変換すると良いです。普通の高速ゼータ変換・メビウス変換の計算量が $O(n2^n)$ で、今回は高々 $n$ 次の多項式を値に取る関数の高速ゼータ変換、高速メビウス変換なので、計算量は $O(2^nn^2)$ です。

$B_n$ では $\rho(x)$ は $x$ のサイズ、$D_n$ では $\rho(x)$ は $x$ の素因数の個数、$V_n(q)$ では $\rho(x)$ は $x$ の次元とできます。$\rho$ はランク関数と呼ばれるものです。半順序集合上の各元 $x$ について、$x$ と最小元 $\hat 0$ を端点に持つ任意の極大鎖の長さが等しいとき、その長さをランク $\rho(x)$ といいます。また、ランクが定義され、任意の元 $s, t$ について、$\rho(s) + \rho(t) = \rho(s\lor t) + \rho(s \land t)$ が成り立つ束をモジュラー束といいます。モジュラー束では
$$\rho(s) + \rho(t) = \rho(s \lor t) \Leftrightarrow s \land t = \hat 0$$となり、意味のある状態が計算できます。$B_n, D_n, V_n(q)$ は全てモジュラー束です。ながたかなさんのブログでも触れられています。

このような、ランクを持ったゼータ変換・メビウス変換を [1] では ranked zeta transform, ranked Moebius transform と呼んでいます。

3つ以上の積の場合も同様に計算できます。また、和・差に関しては線形性があるので、ゼータ変換した各点で計算できます。各点での多項式の計算は $O(n^2)$ でできればよいです。実用上は n が小さく、FFTは定数倍が大きいので避けるべきです。例えば、exp とlog の変換は
\begin{align}
&f=\exp(g)\\
\Longrightarrow&f’=g’f \\
\iff&f_{n+1}=\frac{1}{n+1}\sum_{i=0}^n (i+1)g_{i+1}f_{n-i} \\
\iff&g_{n+1}=f_{n+1}-\frac{1}{n+1}\sum_{i=0}^{n-1} (i+1)g_{i+1}f_{n-i}
\end{align}
のようにして $O(n^2)$ で計算できます。ただし、$f_0=1, g_0=0$ に注意。

練習問題

【問題1】 グラフ $G$ が与えられる。$G$ の彩色数が $m$ 以下であるか判定せよ。

【解答】頂点集合 $S$ が独立集合であるとき、$f(S)=1$ さもなくば $f(S)=0$ となる関数 $f$ を用意します。$f$ の subset convolution の $m$ 乗を求めればよいです。$m$ 乗を各点積で行うことにより、$n$ を頂点数として $O(2^nn^2)$ です。各点で、$m$ 乗以外にも $\exp$ を取ったり、$\log$ を取ったりすることもできます（次の問題）。

※$m$ が定数である場合、より効率的なアルゴリズムが存在しないか検討するべきです（例：ABC 199 問題D）。

【問題2】 グラフ $G$ が与えられる。すべての誘導部分グラフ $G[S]$ に対して、$G[S]$ の全域部分グラフの個数を求めよ。（出典：熨斗袋さん）

【解答】指数型母関数の問題21で解説しています。