Subset Convolution
集合 $S \subseteq \lbrace 0, 1, \ldots, N - 1 \rbrace$ をビットで表した整数を添字として、長さ $2^N$ のリストで表します。 $h(S)$ は、 $T \cup U = S$ となる組を足す OR 畳み込みのうち、 $T \cap U = \emptyset$ となる組だけを足したものです。 $T \cup U = S$ のとき、 $T \cap U = \emptyset$ は $\lvert T \rvert + \lvert U \rvert = \lvert S \rvert$ と同じなので、要素数ごとに分けて考えます。要素数が $i$ の集合での値だけを残した $f_i$, $g_i$ をゼータ変換して $F_i$, $G_i$ とし、 $S$ ごとに $H_k(S) = \sum_{i + j = k} F_i(S) G_j(S)$ を求めます。 $H_k$ をメビウス変換したものの $S$ での値が、 $k = \lvert S \rvert$ のとき $h(S)$ です(ランク付きゼータ変換)。
subset_convolution(f, g, mod): $h(S) = \sum_{T \subseteq S} f(T) g(S \setminus T)$ のリストを返す。 $O(N^2 2^N)$
f と g は同じ長さ( $2$ のべき)にします。各値を mod(既定値は $998244353$)で割った余りで返します。逆元を使わないので、mod は素数でなくてもかまいません。渡したリストは書き換えません。メモリは $O(N 2^N)$ です。
例(頂点の集合 $S$ を 2 つの独立集合 $T$, $S \setminus T$ に分ける方法の数。 $S$ が誘導する部分グラフを 2 色で塗り分ける方法の数です):
N = 3
edges = [(0, 1), (1, 2)]
ind = [1] * (1 << N) # ind[T] = (T が独立集合なら 1、そうでなければ 0)
for T in range(1 << N):
for u, v in edges:
if T >> u & 1 and T >> v & 1:
ind[T] = 0
print(subset_convolution(ind, ind)) # [1, 2, 2, 2, 2, 4, 2, 2]
$T$ と $U$ が交わってもよい OR 畳み込みは XOR・AND・OR 畳み込み で、部分集合にわたる和だけが欲しいときは 高速ゼータ変換・メビウス変換 で求められます。
コード
def subset_convolution(f, g, mod=998244353):
# h[S] = (T ⊆ S についての f[T] g[S - T] の和)。f と g の長さは同じ 2 べき
size = len(f)
n = size.bit_length() - 1
pc = [0] * size # pc[S] = S の要素数
for s in range(1, size):
pc[s] = pc[s >> 1] + (s & 1)
# F[i][S] = (S の部分集合 T で要素数が i のものについての f[T] の和)。G も同じ
F = [[0] * size for _ in range(n + 1)]
G = [[0] * size for _ in range(n + 1)]
for s in range(size):
F[pc[s]][s] = f[s] % mod
G[pc[s]][s] = g[s] % mod
for A in F + G:
w = 1
while w < size:
for i in range(0, size, 2 * w):
for j in range(i, i + w):
A[j + w] += A[j]
w *= 2
for s in range(size):
A[s] %= mod
# S ごとに要素数についての畳み込みをして F に上書きする
# (あとで使うのは要素数 k が S の要素数 c 以上のところだけで、k > 2c なら 0 のまま)
for s in range(size):
c = pc[s]
a = [F[i][s] for i in range(c + 1)]
b = [G[i][s] for i in range(c + 1)]
for k in range(c, min(2 * c, n) + 1):
t = 0
for i in range(k - c, c + 1):
t = (t + a[i] * b[k - i]) % mod
F[k][s] = t
for A in F:
w = 1
while w < size:
for i in range(0, size, 2 * w):
for j in range(i, i + w):
A[j + w] -= A[j]
w *= 2
return [F[pc[s]][s] % mod for s in range(size)]