计蒜客【NOIP2018模拟3】手拉手 <概率DP>

Problem

【NOIP2018模拟3】手拉手

$\mathrm{Time\;Limit:\;1000\;ms}$
$\mathrm{Memory\;Limit:\;131072\;K}$

Description

小 P 是个幼儿园老师。有一天，他组织 $n$ 个小朋友玩游戏。游戏开始时，每个小朋友伸出两只手，没有手相互拉在一起。每次，小 P 等概率随机挑选两只空着的手，让这两只手拉在一起。小 P 一直重复这个操作，直到所有的手都拉在一起。小 P 在成为幼儿园老师之前是个数学专业的博士。因此，他想知道，当所有的手都拉在一起之后，小朋友们拉成的圈个数的期望是多少？其中，我们规定，一个小朋友左手拉右手的情况也形成一个圈。
由于小 P 忙着和小朋友们玩游戏，他找到了聪明的你，希望你能帮他解决这个问题。

Input

输入数据仅一行，包含一个正整数 $n$ ，表示小朋友的数量。

Output

输出文件仅一行，包含一个实数，表示当所有的手都拉在一起之后，小朋友们拉成的圈个数的期望是多少。输出和标准答案的绝对误差不能超过 $10^{-9}$。

Sample Input

Input #1

2

Input #2

1000000

Sample Output

Output #1

1.333333333

Output #2

7.889510292

Hint

Explanation #1
小 P 组织 $2$ 个小朋友玩游戏，我们称他们为小 A 和小 B。小 A 的左手等概率和小 A 的右手、小 B 的左手、小 B 的右手拉在一起，每一种情况的概率均为 $\frac{1}{3}$ 。若小 A 的左右手拉起来，那么最终会形成 $2$ 个圈，因为小 B 也必然左右手拉住。若小 A 的左手和小 B 的任意一只手拉起来，那么最终会形成一个圈，因为小 A 的右手必然和小 B 的另一只手拉住。那么，根据期望的公式，小 A 和小 B 拉成的圈个数的期望为

$$\frac{1}{3}\times2+\frac{1}{3}\times1+\frac{1}{3}\times1=\frac{4}{3}$$

Constraint

对于 $30\%$ 的数据：$1 \le n \le 9$ 。
对于 $50\%$ 的数据：$1 \le n \le 10^3$ 。
对于 $70\%$ 的数据：$1 \le n \le 10^6$ 。
对于 $100\%$ 的数据：$1 \le n \le 10^{18}$。

Source

计蒜客 NOIP 提高组模拟竞赛第二试

标签：概率DP

Solution

用$f[i]$表示$i$个点由上面的方法连边后期望下的环数。
考虑由$i-1$个点的图如何变成由$i$个点的图。可以将第$i$个点加入到任意一条边中间，即把边拆断，用这个点分别连向原来这条边连接的两个点。原来有$i-1$条边，而左右手有区别，所以有$2i-2$种加入的方案，而这样是不会产生新环的。还可以让第$i$个点单独组成自环，共$1$种方案，会产生$1$个新环。于是加入第$i$个点时，有$\frac{1}{2i-1}$的概率产生一个新环。因此有$f[i]=f[i-1]+\frac{1}{2i-1}$。
由此，我们可以$\mathcal{O}(n)$$\text{DP}$，解决$n\le 10^6$的部分分。

对于$n\le10^{18}$的部分，我们将递推式化为和式后化简。

$$\begin{aligned} f[n] &=f[n-1]+\frac{1}{2n-1}\\ &=f[n-2]+\frac{1}{2n-3}+\frac{1}{2n-1}\\ &=\cdots\cdots\\ &=\sum_{i=1}^{n}\frac{1}{2i-1}\\ &=(\sum_{i=1}^{2n}\frac{1}{i})-(\sum_{i=1}^{n}\frac{1}{2}\times\frac{1}{i})\\ &\approx\ln(2n)+\mathcal{C}-\frac{\ln(n)+\mathcal{C}}{2}\\ &=\frac{\ln(n)}{2}+\frac{\mathcal{C}}{2}+\ln(2)\\ \end{aligned}$$

上式中运用了调和级数，其中$\mathcal{C}$为欧拉常数，其约等于$0.57721566490153286060651209$。而在$n\le10^{18}$的情况下我们可以将这个近似值作为答案。由此可以$\mathcal{O}(1)$解得结果。

Code

#include <bits/stdc++.h>
#define MAX_N 1000000
using namespace std;
typedef double dnt;
const dnt C = 0.57721566490153286060651209;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int main() {
    dnt n; read(n);
    if (n <= MAX_N) {
        dnt sum = 0;
        for (dnt i = 1; i <= n; i++)
            sum += 1/(2*i-1);
        printf("%.9lf\n", sum);
    } else printf("%.9lf\n", log(n)/2+C/2+log(2));
    return 0;
}