NOIP2014模拟10.22 – 搞笑的代码 【调和级数】

Problem

在OI界存在着一位传奇选手——QQ,他总是以风格迥异的搞笑代码受世人围观
某次某道题目的输入是一个排列,他使用了以下伪代码来生成数据


聪明的同学一定发现了,这样生成数据是很慢的,那么请你告诉QQ,生成一个n排列的期望随机次数

Solution

定义\(f_i\) 表示序列长度为\( i \)时的期望随机次数,不难根据题目的定义列出递推式,
\[ f_i = \frac{i}{n} (f_i+1) + \frac{n-i}{n} (f_{i-1} + 1) \]
化简可得
\[ f_i = f_{i-1} + \frac{n}{n-i}\]
于是答案就是
\[ \sum_{i=1}^{n}\frac{n}{i} = n \sum_{i=1}^{n}\frac{1}{i} \]
出现了人尽皆知的调和级数求和。我们考虑这里要乘上一个\( n\),\(n\)较小的时候精度要求较高,可以直接递推,\(n\)较大的时候用近似公式\(H_n \sim \ln(n)+\gamma\)即可
没有代码,懒得写

0