2種類の畳み込み subset convolution 資料1 資料2 資料3 ゼータ変換とメビウス変換は逆変換の関係にある ゼータ変換(状態xを含む状態yを全列挙) 高速ゼータ変換でO(n2^n) g[x] = sum{y⊆x}f(y) → rep(i, 0, N) rep(msk, 0, 1 << N) if (msk & (1 << i)) sm[msk] += sm[msk ^ (1 << i)]; g[x] = sum{x⊆y}f(y) → rep(i, 0, N) rep(j, 0, 1 << N) if (!(j & (1 << i))) f[j] += f[j | (1 << i)]; 参考 高速ゼータ変換は環で動く(+, *, max, gcdなど) メビウス変換(状態xの部分状態yを全列挙) 高速メビウス変換でO(n2^n) g[x] = sum{y⊆x}(-1)^|x