#P6836. 树
树
题目描述
有 个位置排成一个圆环,起初都没有树。每次等概率独立地选一个位置并种树。选到已有树的位置也照常计一次。若某个还没有树的位置的两个相邻位置都有树,它会自动长出一棵树。自动长树不占用选择次数。
当每个位置都有树时,游戏结束。求选择次数的期望。 时一次选择即可结束。 时,一个位置的两个相邻位置均指另一个位置。
输入格式
一行一个整数 。
输出格式
一行一个整数,表示期望对 取模的结果。分数 按 计算。
样例
2
1
5
166666673
10
698412717
数据范围
。对于 20%、40%、50%、70% 的数据,依次有 。
YOIP Practice #7。原题面 PDF