×

计蒜客

  1. 题库
  2. 手拉手
  3. 问答
  • 16.23%
  • 131072K

小 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}$。

输入输出样例 1 说明

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

本题答案不唯一,符合要求的答案均正确

要求使用「文件输入输出」的方式解题,输入文件为 hand.in,输出文件为 hand.out

样例输入

2

样例输出

1.333333333

题目来源

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

想挑战这道题吗

  • main.c