考察
現在値そのものを状態にすると 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
出典