https://codeforces.com/contest/1097/problem/D
黒板に書かれた整数$N$の約数の中から等確率で1つを選んで$N$をその約数に書き換える操作を$K$回行ったとき、最後に書かれている整数の大きさの期待値を求めよ。
$N$がある素数$p$を使って$N=p^k$と与えられるとき、期待値は、DPテーブル $$DP[i][j]=i{\rm 回目の操作で}p^j{\rm が残る確率}$$ を使って求められる。
$N$が単一の素数のべきで表せないとき、つまり$N=p^kq^l...r^m$の形で表せるときには、異なる素因数について1回の操作である冪が選ばれる確率はそれぞれ独立であるから、求める期待値は各素因数についての期待値の積で表せる。
(各素因数が1回ずつしかかかっていないとき、操作は各素因数をそれぞれ1/2の確率で取り除く操作であると考えることができるので素因数ごとに独立と考えられるが、2回以上かかっている素因数についてはこれが成り立たない(たとえば、$4=2\cdot2$について、2をそれぞれ等確率で取り除くことと1,2,4をそれぞれ1/3の確率で選択することは異なる。))
素因数ごとに独立であることはわかったが、DPテーブルを発想できなかったのは駄目。