[LightOJ]Race to 1 Again(期望DP)

发布于 2022-05-03  1495 次阅读


传送门: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;
}