LightOJ 1038 Race to 1 Again (简单期望)

hhhh传送门

一个数的因子有$num$个,分别是$a_1,a_2..,a_{num}$

定义$dp[i]$为$i$转换为$1$的期望次数

$dp[i]=\frac{dp[a_1]+dp[a_2]...+dp[num]}{num}+1$

其中$dp[num]=dp[i](i==num)$

所以移项可解得$dp[i]$

#include <bits/stdc++.h> using namespace std; const int maxn=2e5+10; int t,n,a[maxn],num[maxn]; double dp[maxn]; void print() { for(int i=1;i<=100000;i++) for(int j=i;j<=100000;j+=i) num[j]++; } int main() { print(); cin >> t; int casenum=0; while( t-- ) { int top = 0; cin >> n; for(int i=1;i<=n/2;i++) if( n%i==0 ) a[++top]=i; a[++top] = n; for(int i=2;i<=top;i++) { for(int j=1;j<i;j++) { if( a[i]%a[j]!=0 ) continue; dp[i] += ( dp[j]+1 )/num[ a[i] ]; } if( num[ a[i] ]==1 ) continue; double x = 1.0/num[a[i]]; dp[i] = ( dp[i]+x )/(1-x); } printf("Case %d: %.7lf\n",++casenum,dp[top] ); for(int i=1;i<=top;i++) dp[i]=0; } }