傳送門

剛剛學習期望&概率

我們設數X的期望改變次數為P[X]

如果要求X的期望，很容易想到找x的因子;

可以得到下式

?,cnt為X因子個數，ai為X的因子

可以這么理解，當因子ai為1時，因為除于1不改變其期望值,上式上邊分子部分為1+P[1]+P[x]

不為1時，上部分為p[ai]+1，相當于把狀態轉換過去，并且期望次數加1

分母為cnt，即為包括1和n的因子個數，因為該點可以由所有因子轉化而來
經過化簡可得

?

哈哈，這個時候就是可以用素篩的思想來進行求解。

預處理所有p[i]

第一次自己推出來，開心

#include<stdio.h>
#include<string.h>
#include<string>
#include<iostream>
#include<algorithm>
#include<math.h>
#include<set>
#include<stack>
#include<vector>
#include<map>
#include<queue>
#include<functional>
#pragma comment (linker,"/STACK:102400000,102400000")
#define myself i,l,r
#define lson i<<1
#define rson i<<1|1
#define Lson i<<1,l,mid
#define Rson i<<1|1,mid+1,r
#define half (l+r)/2
#define lowbit(x) x&(-x)
#define min4(a,b,c,d) min(min(a,b),min(c,d))
#define min3(x,y,z) min(min(x,y),min(y,z))
#define max4(a,b,c,d) max(max(a,b),max(c,d))
#define max3(x,y,z) max(max(x,y),max(y,z))
#define pii make_pair
#define pr pair<int,int>
typedef long long ll;
typedef unsigned long long ull;
const int inff=0x3f3f3f3f;
const long long inFF=9223372036854775807;
const int dir[4][2]={0,1,0,-1,1,0,-1,0};
const double eqs=1e-9;
const double E=2.718281828459;
const double pi=acos(-1.0);
const int maxn=1e5+5;
const int mod=1e9+7;
using namespace std;
double p[maxn];
int cnt[maxn];
void init()
{p[1]=0;for(int i=2;i<maxn;i++){p[i]=(p[i]+cnt[i]+2)/(cnt[i]+1);for(int j=2*i;j<maxn;j+=i)p[j]+=p[i],cnt[j]++;}
}
int main()
{int t,n,cas=0;init();cin>>t;while(t--){cin>>n;printf("Case %d: %.7f\n",++cas,p[n]);}return 0;
}

AC代碼：

?

總結

以上是生活随笔為你收集整理的LightOJ - 1038 Race to 1 Again 基础期望概率 dp的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。