【LightOJ-1038-Race to 1 Again?】概率期望DP

LightOJ-1038-Race to 1 Again

题意

给你一个数字，每次这个数字会等概率地变成他的某个因子，问这个数字变为1的期望步数。

做法

期望DP的固定做法，从后往前DP，首先dp[1]=0，之后每个数字选中他每一个因子的概率相等，设数字x变为1的期望为dp[x]，那么我们可以得到等式

$dp[x]={\sum }_{d|x}dp[d]+1$
$dp[x]=\frac{{\sum }_{d|x\cap d<x}(dp[d]+1)}{x}+\frac{dp[x]+1}{x}$

解方程即可得到转移式，时间复杂度$O(n\log n)$

代码

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
const int maxn = 1e5+5;
const int Mod=1000000007;
double dp[maxn];
vector<int> G[maxn];
int main()
{
    for(int i=1;i<=100000;i++){
    for(int j=i;j<=100000;j+=i){
    G[j].push_back(i);}}for(int i=2;i<=100000;i++){
    int cnt=G[i].size();for(int j=0;j<G[i].size()-1;j++){
    dp[i]=dp[i]+1.0*(dp[G[i][j]]+1.0)/cnt;}dp[i]=dp[i]+1.0/cnt;dp[i]=1.0*dp[i]*cnt/(cnt-1);}int t;scanf("%d",&t);int cc=0;while(t--){
    int n;scanf("%d",&n);printf("Case %d: %.10f\n",++cc,dp[n]);}return 0;
}