LightOJ 1038 概率dp
2024-08-27 01:54:05
题意:给一个数n,每次除它的一个因子(等概率),问除到1的次数的期望是多少
题解:概率dp,对于一个数x,y是x的因子个数,因子是a1到ay,E(x)=(E(a1)+1)/y+...+(E(ay)+1)/y,复杂度O(nsqrt(n))
#include<bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pi acos(-1.0)
#define ll long long
#define mod 1000000007
#define C 0.5772156649
#define ls l,m,rt<<1
#define rs m+1,r,rt<<1|1
#define pii pair<int,int> using namespace std; const double g=10.0,eps=1e-;
const int N=+,maxn=+,inf=0x3f3f3f3f; double dp[N];
vector<int>v[N];
int main()
{
for(int i=;i<=;i++)
{
for(int j=;j*j<=i;j++)
{
if(i%j==)
{
v[i].pb(j);
if(j*j!=i)v[i].pb(i/j);
}
}
}
for(int i=;i<=;i++)
{
double te=;
for(int j=;j<v[i].size();j++)
{
int x=v[i][j];
te+=+dp[x];
}
dp[i]=te/(v[i].size()-);
}
int res=,t;
scanf("%d",&t);
while(t--)
{
int n;
scanf("%d",&n);
printf("Case %d: %.10f\n",++res,dp[n]);
}
return ;
}
/******************** ********************/
最新文章
- The prefix ";util"; for element ";util:list"; is not bound.
- Masonry 创建Button的简单使用
- opencv 中对一个像素的rgb值或像素值进行操作的几个常用小办法【转】
- JQ中的延迟对象deferred中的promise等的使用
- Stack的pop和push操作
- SGU 105 div.3 找规律
- prototype原型模式中的问题
- iOS添加自定义字体方法
- 最简单的CRC32源码---逐BIT法
- Web日程管理FullCalendar
- OpenGL多视口
- java 静态资源访问详解
- cookie跨域共享
- Spring Security 案例实现和执行流程剖析
- leetcode240
- ZJOI2019 Day1 题解
- Ubuntu下好的PDF阅读器介绍
- 获取QQ头像接口
- ABP框架入门踩坑-使用MySQL
- SVN无法读取cruuent修复方法
热门文章
- 我的Android进阶之旅------>解决Bug:打开eclipse报错,发现了以元素 'd:skin' 开头的无效内容。此处不应含有子元素。
- 于win2008R2虽然激活,但是一个小时之后就会自动强制关机的问题
- ZOJ 3958 Cooking Competition 【水】
- PAT 天梯赛 L1-034. 点赞 【MAP】
- Python学习进程(4)运算符
- 每天一个Linux命令(55)systemctl命令
- $ 用python处理Excel文档(1)——用xlrd模块读取xls/xlsx文档
- sudoers文件设置sudo命令无密码(root密码)登录
- Java技术路线
- MySQL-LRU_List Free_List Flush_List