ABC 239 Ex — Dice Product 2

考察

現在値そのものを状態にすると M 個必要だが、現在の積 p から停止せず掛けられる上限 x=floor(M/p) だけで未来は決まる。出目 i の後はこの上限が floor(x/i) へ移る。

出目1では状態 x に留まる自己ループがあるため、期待値式の f(x) を右辺から移項すると f(x)=(N+Σ_{i=2}^N f(floor(x/i)))/(N-1) になる。

採用する候補: floor(x/i) が同じになる出目区間をまとめ、f(M) から必要になった商状態だけを memoize する。

一状態の和を quotient block ごとに計算でき、再帰で現れる状態も floor(M/d) の形に閉じて約平方根個に限られる。

棄却する候補: 各状態 x で出目1..Nを全て走査し、x=0..M の期待値を順に計算する。

N,M はともに10^9まであり、状態数も一状態の遷移数も列挙できない。

floor(floor(M/i)/j)=floor(M/(ij)) なので、memo 再帰を何段進めても引数は M をある正整数で割った商になり、新しい任意の整数状態は現れない。

l を区間先頭、q=floor(x/l) とすれば同じ商を持つ末尾は floor(x/q) であり、N までに切って multiplicity を一括加算できる。

f(0)=0 とし、未計算の x では i=2 から min(N,x) までを quotient block [l,r] に分け、(r-l+1)f(floor(x/l)) を加える。N とこの和を足して N-1 の法逆元を掛け、map に memoize して f(M) を返す。

典型の発動条件

商が一定な区間の一括処理

発動条件: Σ f(floor(n/i)) のように切り捨て商だけが遷移先を決めるとき。

次の境界 r=floor(n/floor(n/l)) を使って同じ商の係数をまとめる。

期待値 DP の自己ループ除去

発動条件: 確率遷移に同じ状態へ戻る結果が含まれるとき。

自己遷移確率を左辺へ移し、未確定の f(x) が右辺に残らない式へ解く。

問題固有の要素

積の進行を残り許容倍率 floor(M/p) へ反転すると、掛け算が切り捨て除算の遷移になり、商集合の少なさを使える。

別の問題へ持ち帰る視点: 値が単調に乗算される過程では、閾値までの余裕を商で表すと状態圧縮できないか考える。

正当性

積pの後に掛けられる上限x=floor(M/p)が将来を全て決める。出目1の自己ループを移項するとf(x)=(N+Σ_{i=2}^N f(floor(x/i)))/(N−1)。i≥2では状態が減るので再帰が停止する。同じ商を持つ区間の項は同値なため個数を掛けてまとめても和は変わらず、商集合の閉性でmemoが全必要状態を網羅する。

実装上の注意

  • i=1 の自己ループを quotient loop に含めない。i>x の項は f(0)=0 なので省略でき、block 末尾は min(N,floor(x/q)) とする。係数と期待値は法10^9+7で正規化する。

復習の核

  • N=2 の式で出目1のやり直しを左辺へ移し f(1)=2 を導いてから、nested floor が一つの除数積へ潰れることを再確認する。

計算量と制約

時間

O(Σ_{x∈Q}√x)≤O(M^{3/4})を上界とする。Q={floor(M/d)}で、各状態を商区間走査する。

空間

O(√M)。商状態のmemo表。

制約との対応

公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 2 \leq N \leq 10^9; 1 \leq M \leq 10^9

出典

分類・前提・執筆情報

掲載状態: 収録済み

Dice Product 2 の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 整数境界と同値区間を正確に分ける

主題
追加で学ぶ技能
    なし
    既習技能
    • 法上の四則演算・高速累乗・逆元: 剰余を正規化して加減乗算し、二分累乗と可逆性を確認した逆元により法上の除算・確率を計算できる。
    • 確率過程・期待値DP: 状態から先の期待費用・期待回数を定義し、一歩分の費用と未来の期待値を分け、自己ループを移項した方程式を解ける。

    主タグ: 整数境界・同値区間分割

    補助タグ: 法上の四則演算・高速累乗・逆元 確率・期待値DP

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

    学習の位置

    体系上の位置: 整数境界と同値区間を正確に分ける

    • floor(N/i)が一定の最大区間を整数除算で列挙し、O(√N)個の区間へ集約できる。整数根・桁数の境界も誤差なく扱える。

    先に読む単元:

    この解説で扱わないこと:

    • 素因数指数による整数条件の分解。

    学習記録

    状況更新: 更新記録なし

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

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

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

    同じ単元の問題