彩色数のはなし

自分用のメモ

彩色数を求めたい。まず塗る色の種類数kを固定する。
I(S):=Sの部分集合であって、独立なものの種類数
f(S):=Sの部分集合であって、独立なものを重複ありでk個集めてくる場合の数
g(S):=Sの部分集合であって、独立なものを重複ありでk個集めてきたもの、ただしそれらの和集合がちょうどSに一致する場合の数
明らかにf(S)=I(S)^k、gとfはゼータ変換、メビウス変換の関係にある
また、I(S)はSに含まれる頂点を一つ取れば、それを含む場合+含まない場合で書き尽くせる　つまりbitDPで求まる
ここから、g(all)が1以上になる最小のkを探せば良い(ここに二分探索が使えるが、計算量はさほど良くならない)

ACPC2021Day1-Bは同様の考え方が適用できる
長さNのbit列がM本あったとき、いくつか選んでorをとり、全てのbitが1になるようにしたい　最小の選ぶ本数は何本か？という問題
残す数の個数をkとする
I(S):=A[i]がSの部分集合であるようなiの数
f(S):=A[i]がSの部分集合であるようなiを重複ありでk個集めてくる場合の数
g(S):=A[i]がSの部分集合であるようなiを重複ありでk個集めてきたもの、ただしそれらの和集合がちょうどSに一致する場合の数
今回のIはゼータ変換で求まり、f,gは前と同様

この2つが似た方針になるのは、
彩色数は隣接しない条件を満たすようなbit列を最小本数とってorでallにする問題だから