「题解」随机数生成器

一道神奇的 期望概率 DP 题,需要用到 欧拉常数

题目链接:Luogu P5147

题目

题意简述

有一个函数 $\operatorname{work}(n)$。

它的表达式如下。

$$\operatorname{work}(n)=\begin{cases}0,n=1\
\text{work}(\operatorname{rand}(1,n))+1,n\neq 1\end{cases}$$

其中 $\operatorname{rand}(l,r)$ 表示等概率的区间 $[l,r]$ 内的一个正整数。

求 $\operatorname{work}(n)$ 的数学期望,保留小数点后五位。

数据范围

$$1\leq n\leq 2^{31}-1$$

时空限制

$$\text{Luogu}:1\text{s}/125\text{MiB}$$

题解

思路

推式子。

设 $\operatorname{work}(n)$ 的数学期望为 $f(n)$。

那么可以得出

$$f(n)=1+\frac{\sum^{n}_{i=1}f(i)}{n}$$

化简得

$$f(n)=(1+\frac{\sum^{n-1}_{i=1}f(i)}{n})\times \frac{n}{n-1}$$

这样就可以以渐进时间复杂度为 $\Theta(n)$ 的时间递推了。

代码:

#include<bits/stdc++.h>
using namespace std;
#define reg register

int n;

int main(void){
    scanf("%d",&n);
    reg double ans=0,sum=0;
    for(reg int i=2;i<=n;++i){
        ans=(1.0+sum/i)*i/(i-1);
        sum+=ans;
    }
    printf("%.5f\n",ans);
    return 0;
}

但是考虑本题的数据范围,这还不够。

于是下面诞生了两种解题方法。

思路 A(欧拉常数)

观察递推式,发现

$$f(n)=1+\sum^{n-1}_{i=1}\frac{1}{i},n\geq 2$$

下面证明这个猜想。

首先,根据递推式

$$f(2)=2$$

下面考虑

$$f(n+1)=(1+\frac{\sum^{n+1}{i=1}f(i)}{n+1})\Leftrightarrow (n+1)f(n+1)=(n+1)+\sum^{n+1}{i=1}f(i)$$

$$f(n)=(1+\frac{\sum^{n}{i=1}f(i)}{n})\Leftrightarrow nf(n)=n+\sum^{n}{i=1}f(i)$$

$$(n+1)f(n+1)-nf(n)=(n+1)+\sum^{n+1}{i=1}f(i)-n-\sum^{n}{i=1}f(i)$$

移项化简

$$(n+1)f(n+1)-nf(n)=1+f(n+1)$$

$$nf(n+1)-nf(n)=1$$

$$f(n+1)-f(n)=\frac{1}{n}$$

得证。

所以我们有

$$f(n)=1+\sum^{n-1}_{i=1}\frac{1}{i},n\geq 2$$

可是这还是 $\Theta(n)$ 的,不过我们可以通过 欧拉常数 对式子进行有损精度的化简。

理论基础:

$$\lim {n\to +\infty} \sum^{n}{i=1}\frac{1}{i}-\ln(n)=\gamma$$

其中 $\gamma$ 约等于 $0.57721566490153286$。

于是当 $n$ 足够大的时候,可以用 $\ln(n)+0.57721566490153286$ 代替 $\sum^{n}_{i=1}\frac{1}{i}$。

实验表明,当 $n \geq 10^5$ 时,精度已经足够了。

代码

代码比较简短。

#include<bits/stdc++.h>
using namespace std;
#define reg register

int n;

int main(void){
    scanf("%d",&n);
    reg double ans=0;
    if(n<100000)
        for(reg int i=1;i<n;++i)
            ans+=1.0/i;
    else
        ans=log(n)+0.577215664901532;
    printf("%.5f\n",n==1?0:ans+1);
    return 0;
}

思路 B(分块打表)

考虑到

$$f(n)=1+\sum^{n-1}_{i=1}\frac{1}{i},n\geq 2$$

我们可以分块打表 $\sum^{n-1}_{i=1}\frac{1}{i}$,其中块的大小为 $2^{16}$。

所以算法的渐近时间复杂度为 $\Theta(\sqrt{n})$,空间复杂度为 $\Theta(\sqrt{n})$。

代码

打表时间约为 $\frac{2^{31}}{4\times 10^7}\text{s}$,即大约 $53\text{s}$,也够快的。

略。