勉強会に参加したい方は 概要 を確認してください。

定期宣伝

弊社はエンジニアを熱烈募集しています． 以下から気軽にカジュアル面談申し込んでください． 就職・転職を考えている知人にも積極的に宣伝してください．

Spir | Smart scheduling calendar

この勉強会の宣伝もお願いします． 参加者が増えるほど質や頻度が上がると思います． #Acompany競プロ勉強会 で実況や感想，質問を呟くなども．

今までの冪級数・母関数入門

• 231107_形式的冪級数入門
• 241119_指数型母関数入門

以下では $2^n$ で $\{0,1,\dots, n-1\}$ の部分集合全体も指すことにする。

例えば $2^2 = \{\empty, \{0\}, \{1\}, \{0,1\}\}$ となる。

Subset Convolution

集合 $S,T$ が $S\cap T = \emptyset$ を満たす時、その和 $S\cup T$を特別に $S\sqcup T$ で表すことにする。（非交和）

関数 $a,b : 2^n \to K$ に対して、その積 $a \otimes b : 2^n \to K$ を以下で定める：（ $K$ は適当な環）

$$ a \otimes b(U) \coloneqq \sum_{S\sqcup T = U} a(S)b(T) $$

この操作は Subset Convolution と呼ばれている。

コードで書くと以下のような操作である。

def naive_subset_convolution(a: list, b: list):
		c = [0] * len(a)
		for i in range(a):
				for j in range(b):
						if i&j == 0:
								c[i|j] += a[i] * b[j]
		return c