期待値
問題 問題概要 自然数Nに対し次の操作をK回繰り返す. K回後の期待値を求めよ. 自然数に対してその約数を等確率で1つ選び,その約数で置き換える. 1 <= N <= 1015 , 1 <= K <= 104 解法 本番は愚直なDPを定数倍高速化しようとしたが無理だった. これは約数を全…
問題 問題概要 自然数Nに対し次の操作をK回繰り返す. K回後の期待値を求めよ. 自然数に対してその約数を等確率で1つ選び,その約数で置き換える. 1 <= N <= 1015 , 1 <= K <= 104 解法 本番は愚直なDPを定数倍高速化しようとしたが無理だった. これは約数を全…