問題 解法 お絵描きしたのでメモ. 部分点は O(N2) の区間DP. それ以上に早くやるにはどうするか. 遷移が O(1) なので状態を減らすしかない. しかし,DPテーブルは疎でもなく,あまりまとめられそうにもない. よってある状態(操作)を禁止して状態を減らすことを…
問題 問題概要 自然数Nに対し次の操作をK回繰り返す. K回後の期待値を求めよ. 自然数に対してその約数を等確率で1つ選び,その約数で置き換える. 1 <= N <= 1015 , 1 <= K <= 104 解法 本番は愚直なDPを定数倍高速化しようとしたが無理だった. これは約数を全…
引用をストックしました
引用するにはまずログインしてください
引用をストックできませんでした。再度お試しください
限定公開記事のため引用できません。