ErikTse Runtime

  • 首页 / Home
  • | 算法学习 / Algorithm
    • 所有 / All
    • 简单 / Easy
    • 中等 / Medium
    • 困难 / Hard
  • | 技术分享 / Technology
    • 所有 / All
    • 网络技术 / NetWork
    • 资源共享 / Resource
    • 项目实践 / Event
Keep Going.
温故而知新.
  1. 首页
  2. 算法学习
  3. 中等
  4. 正文

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

2022年5月3日 1386点热度 0人点赞 0条评论

传送门: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;
}
本作品采用 知识共享署名-非商业性使用 4.0 国际许可协议 进行许可
标签: C++ DP lightoj 动态规划 期望dp 算法竞赛
最后更新:2022年7月9日

Eriktse

19岁,性别未知,ACM-ICPC现役选手,ICPC亚洲区域赛银牌选手,CCPC某省赛铜牌蒟蒻,武汉某院校计算机科学与技术专业本科在读。

点赞
< 上一篇
下一篇 >

文章评论

razz evil exclaim smile redface biggrin eek confused idea lol mad twisted rolleyes wink cool arrow neutral cry mrgreen drooling persevering
取消回复

订阅本站
Loading
文章目录
  • 题目 / Problem
  • 思路 / Thought
  • 代码 / Code

COPYRIGHT © 2022 ErikTse Runtime. ALL RIGHTS RESERVED.

Theme Kratos Made By Seaton Jiang

赣ICP备2022001555号-1

赣公网安备 36092402000057号