Race to 1 Again 期望

题目

Rimi learned a new thing about integers, which is - any positive integer greater than 1 can be divided by its divisors. So, he is now playing with this property. He selects a number N. And he calls this D.

In each turn he randomly chooses a divisor of D (1 to D). Then he divides D by the number to obtain new D. He repeats this procedure until Dbecomes 1. What is the expected number of moves required for N to become 1.

大概就是说一个数每次除以他的因子,问这个数变为1的步数期望

题解

期望倒着推,概率正着推

很有趣的一道题,和杭电上的飞行棋那题有点像.

很显然:ex[1]=0

然后我们考虑2: 2可以到达1,2,那么ex[2]=$\frac{1}{2} $ex[1]+$\frac{1}{2}$ex[2]+1.

因为2可以到达1或者2概率都为1/2,然后再加上这次所花费的步数1.

同理 ex[6]=$\frac{1}{4}$ex[1]+$\frac{1}{4}$ex[2]+$\frac{1}{4}$ex[3]+$\frac{1}{4}$ex[6]+1.

代码

//感觉这种记忆化写法挺常见的,以前在区域赛写过一次,
#include<cstdio>
const int MAXN=1e5+7;
double ex[MAXN];
double dfs(int x){
	if(ex[x]>0)return ex[x];
	if(x==1)return ex[1]=0;
	//printf("x=%d\n",x);
	int stack[500],top=0,i;//这个地方开始开的50,爆炸了
	for( i=1;i*i<x;++i){
		if(x%i==0){
			stack[top++]=i;
			stack[top++]=x/i;
		}
	}
	if(i*i==x)stack[top++]=i;
	double res=top;
	for(int j=0;j<top;++j){
		if(stack[j]!=x)res+=dfs(stack[j]);
	}
	return ex[x]=res*1.0/(top-1);
}
int main(){
	int T;scanf("%d",&T);
	for(int test=1;test<=T;++test){
	//	for(int x=1;x<=100000;++x){
			int x;scanf("%d",&x);
		//	printf("x=%d\n",x);
			ex[1]=0.0;
			printf("Case %d: %.7f\n",test,dfs(x));

		//}
	}
	return 0;
}