ABC 423 F — Loud Cicada

考察

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.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Loud Cicada の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: subset zeta・Möbius変換

主題
  • subset zeta・Möbius変換: Boolean lattice上のsubset/superset和とexact値をzeta変換・Möbius反転で相互変換する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。
追加で学ぶ技能
    なし
    既習技能
      なし

      主タグ: subset zeta・Möbius変換

      執筆: abc-explanation-author1.1.1 / revision 1

      学習の位置

      体系上の位置: subset zeta・Möbius変換

      • Boolean lattice上のsubset/superset和とexact値をzeta変換・Möbius反転で相互変換する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。

      先に読む単元:

      学習記録

      状況更新: 更新記録なし

      復習設定更新: 更新記録なし

      端末内の保存状態を確認しています。

      要復習一覧 / 学習記録のバックアップ / 解説に戻る

      同じ単元の問題