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)$ です(ランク付きゼータ変換)。

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)]