Hello 2019 D. Makoto and a Blackboard

• 問題

問題概要

自然数Nに対し次の操作をK回繰り返す. K回後の期待値を求めよ.

• 自然数に対してその約数を等確率で1つ選び,その約数で置き換える.

1 <= N <= 10¹⁵ , 1 <= K <= 10⁴

解法

本番は愚直なDPを定数倍高速化しようとしたが無理だった.

これは約数を全列挙した後, dp[ i ][ j ] := ( i 回目の操作で j 番目の約数である確率,または期待値 ) とやるDP.
約数の数 S とすると, S 〜 2¹³ 〜 8 * 10³ 程度なので( 13番目の素数までの積〜 10¹⁵ より )
配るDPでやると複数区間に配ることになり,連続区間でなくimos法も使えないので O( S² * K ) で間に合わない.

Hello 2019 Editorial - Codeforces にもあるように,各素因数が独立であることを使って計算しよう.

X,Y が独立の時, E[XY] = E[X]E[Y] より, 操作後の値 X= 2^a 3^b 5^c ... とすれば
E[X] = E[ 2^a 3^b 5^c .. ] = E[2^a] E[3^b] E[5^c] .. となって各々DPで計算すれば良い.

a, b, c, .. = O( logN ) より, 全体での計算量は Q = |全体での素因数|と すると
愚直にやっても O( Q * log² N * K ) となって
さっき見たように Q〜 13程度なので十分間に合う.
imos法も簡単に使えるので O(Q * logN * K) となる.
ちなみに元の計算量は S = O( log^Q N) なので O( log^2Q N * K ) である.(最初よりも緩い見積もり)
状態を複数の独立な状態に分割することによって計算量を落としていることがわかる.
期待値の問題でよく使えそうなので覚えておきたい.

メモ

本番では 最後ありえる状態に対してその確率をなんとかして数えたい
↓ 6 ~(2回の操作)~> 1 に対して
6->6->1, 6->3->1, 6->2->1, 6->1->1 を数える?と思っていたが,
各パスが遷移の確率が等しくないので困っていた.

素因数独立に見るのは少し考えたが回答までたどり着かなかった.
状態数が落ちるのが明確にイメージできてなかったせいだと思う.

ちなみに愚直DPを行列累乗で高速化すると O( S² logK ) になるが間に合わないらしい.

コード