【计蒜客 NOIP 提高组模拟竞赛第二试】手拉手 / 题解

原题地址

题目描述

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

由于小 P 忙着和小朋友们玩游戏,他找到了聪明的你,希望你能帮他解决这个问题。

输入格式

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

输出格式

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

数据规模与约定

对于 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}$。

输入输出样例说明

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

思路

一、计数部分

证明思路:
  • 核心问题 : n 个点时环的总数 $f_n$
  • 方法: 建立递推关系
推导过程

新加入点 $V_n$,由 $f_{n-1}$ 推至 $f_n$。

① $V_n$ 自环

令 $g_n$ 为此时环的个数,$\sigma_{n-1}$为 $n-1$ 个点的所有排列方法,有

$$g_n=f_{n-1}+\sigma_{n-1}$$

② $V_n$ 不自环

对于 $∀E∈G_{n-1}$,考虑它的两个端点 $V_x$,$V_y$,插入 $V_n$ 的过程如图:

发现在操作前后,环的数量没有增加。而 $V_n$ 共有 $n-1$ 个可行的插入点,并且由于 $V_n$ 有左右手之分,令此时不同的环的个数为 $h_n$,有

$$h_n=2(n-1)f_{n-1}$$

综上,我们得到:

现在我们可以考虑期望部分了。

记期望为$\varepsilon_n$,有

$$\varepsilon_n \cdot \sigma_n = (2n-1)\varepsilon_{n-1} \sigma_{n-1} + \sigma_{n-1}$$


下面求 $\sigma_n$。

对于 $n$ 个小朋友,我们实际上是在 $2n$ 个相对独立的点之间连边。由于每次连边是等概率随机,易得$\sigma_n=(2n-1) \cdot (2n-3) \cdot (2n-5) \cdots 1 = (2n-1)!!$。


现在我们可以继续化简期望的公式。

二、计算部分

我们成功地求得了期望的递推式,但是根据数据范围,我们不能用 $O(n)$ 的方法计算答案。于是我们观察这个式子,发现它实际上是两个调和级数 $Harmonic \ series$ 相减的结果。当 n 很大的时候,我们可以这样化简它:

其中,$C$ 为欧拉常数,近似值为0.57721566490153286060651209。这个计算方式在 $n$ 大于 $1000000$ 时精度已经足够了。

代码

#include 
#define ld long double 
using namespace std;
ld fp,fn;
void Hi(long long n){
    fp=fn=1;
    for (int i=2;i<=n;i++)
        fn=(ld)1/(2*i-1)+fp,fp=fn;
}
int main(){
//  freopen("hand.in","r",stdin);
//  freopen("hand.out","w",stdout);
    long long n;
    cin>>n;
    if (n<1000000){
        Hi(n);
        printf("%.10Lf\n",fn);
    }
    else{
        ld tem=+log(2)+log(n)/2.0+0.57721566490153286060651209/2.0;
        printf("%.10Lf\n",tem);
    }
    return 0;
}