#P3830. [SHOI2012] 随机树

    ID: 4571 远端评测题 1000ms 128MiB 尝试: 0 已通过: 0 难度: 6 上传者: 标签>动态规划 DP2012各省省选上海期望构造

[SHOI2012] 随机树

题目背景

SHOI2012 D1T3

题目描述

输入格式

输入仅有一行,包含两个正整数 q, n,分别表示问题编号以及叶结点的个数。

输出格式

输出仅有一行,包含一个实数 d,四舍五入精确到小数点后 6 位。如果 q = 1,则 d 表示叶结点平均深度的数学期望值;如果 q = 2,则 d 表示树深度的数学期望值。

输入数据 1

1 4

输出数据 1

2.166667

输入数据 2

2 4

输出数据 2

2.666667

输入数据 3

1 12

输出数据 3

4.206421

输入数据 4

2 12

输出数据 4

5.916614

提示