考察
year yが条件iを満たすのはA_i|yである。subset Tの全条件を少なくとも満たすyear数はlcm(A_i,i∈T)の倍数個floor(Y/lcm)で求まり、exact satisfied subsetへMöbius inversionできる。
採用する候補: 全subset LCMを作りsuperset Möbius transformする
N≤20なので2^N状態で各yearを列挙せず、exactly M条件の年数を得られる。
棄却する候補: 1…Yの各yearで全A_iを試す
Yは10^18まであり列挙不可能である。
F[T]=全i∈Tを満たす年数とG[S]=exactにSを満たす年数にはF[T]=Σ_{S⊇T}G[S]が成り立つ。superset Möbius inversion後、popcount(S)=MのG[S]を合計すればよい。
subset DPでlcm[mask]を一bit追加から計算し、Y超ならY+1へcapする。F[mask]=Y/lcm[mask]を作り、各bitについてmaskにbitなし側からあり側を引くsuperset Möbius transformでGへ変換し、popcount Mを合計する。
典型の発動条件
subset LCM DP
発動条件: 条件subsetの同時成立が数のLCMによる倍数条件になる。
一bit除いたsubsetのLCMと新Aをgcdで安全に更新する。
superset Möbius inversion
発動条件: at least指定条件のcountからexactly成立条件集合のcountを復元する。
F[T]=Σ_{S⊇T}G[S]をBoolean lattice上で反転する。
問題固有の要素
求めるexactly M speciesは単なるM個subset inclusion-exclusionを個別にせず、全exact maskを一括反転してpopcountで集約できる。
別の問題へ持ち帰る視点: exact条件数queryはexact satisfied-set distributionをsubset transformで復元する。
正当性
年yが全T条件を満たす数F[T]はLCMの倍数数。exact成立集合Sが一意なのでF[T]=Σ_{S⊇T}G[S]。superset反転がこの累積関係を逆にし、popcount MのGだけ合計すればexactly M条件年を数える。Y超LCMは倍数を持たないのでY+1capで個数0を保存する。
実装上の注意
- lcm計算はx/gcd(x,a)>Y/aならY+1へcapしoverflowを避ける。empty maskのlcmは1。
復習の核
- N小・Y小でyear列挙し、重複A、A_i>Y、包含関係を比較する。
計算量と制約
時間
O(N2^N+2^N log max A_i)。subset LCMとsuperset Möbius反転。
空間
O(2^N)。
制約との対応
公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 1 \leq M \leq N \leq 20; 1 \leq Y \leq 10^{18}; 1 \leq A_i \leq 10^{18} (1 \leq i \leq N); All input values are integers.
出典