[LightOJ]Race to 1 Again（期望DP）

传送门：http://www.lightoj.com/volume_showproblem.php?problem=1038

题目 / Problem

有T组用例。给定一个正整数N(1 <= N <= 1e5)，每次N可以等概率得除以一个因子，从而变成一个新的N，问从N变到1的次数期望。

次数期望是说，假如现在是第 i 轮变换，那么这一次(x - > y)对于结果的贡献是i * p(x -> y)，p(x -> y)为 x 变换到 y 的概率。

思路 / Thought

用f[i]表示从i变换到1的次数期望，从前往后推。

假设现在要求f[x]，那么先求出x的因子，复杂度为O(sqrt(x))，设因子分别为a1,a2,a3.....am，不难发现a1 == 1, am == x。

那么现在x变成任意一个因子的概率为1 / m，现在假设路线为x -> a1 -> ... -> 1，那么期望为1 / m * (1 + f[a1])，也就是说有1 / m的概率，通过走(1 + f[i])步到达点1。

整理一下得到

然后把f(x)放一边，得到

预处理一下就可以了。

代码 / Code

/*Copyright (C) Eriktse 2022*/
#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define int long long
using namespace std;
inline int readInt()
{
	int s = 0, w = 1;char ch = getchar();
	for(;ch  < '0' || ch >  '9';ch = getchar())if(ch == '-')w = -1;
	for(;'0' <= ch && ch <= '9';ch = getchar())s = s * 10 + ch - '0';
	return s * w;
}

const int maxn = 1e5 + 9;

double f[maxn];
int kase = 1;

vector<int> getyz(int x)
{
	vector<int> res;
	for(int i = 1;i <= x / i; ++ i)
	{
		if(x % i == 0)
		{
			res.pb(i);
			if(i * i != x)res.pb(x / i);
		}
	}
	return res;
}

void init(int N)
{
	f[1] = 0;
	for(int x = 2;x <= N; ++ x)
	{
		vector<int> yz = getyz(x);
		double sum = 0;
		for(auto i : yz)sum += f[i];
		int m = yz.size();
		f[x] = (sum + m) / (m - 1);
	}
}

signed main()
{
	init(maxn - 5);
	int T = readInt();	
	while(T --)
	{
		int x = readInt();
		printf("Case %lld: %.8lf\n",kase ++, f[x]);
	}
	return 0;
}