LR突然想要吃葡萄
事情要从很久很久以前的一次吃水果说起。
百无聊赖的LR在昨天（很久？）买了一大串葡萄，绿色的葡萄看起来鲜嫩多汁，好吃极了。LR没能忍住，于是当天晚上就立刻想要洗葡萄吃。
找室友借来一个小托盘，把葡萄一颗颗剥下来，丁零当啷放进去，打开水龙头，哗哗的自来水冲了下来，LR开始开心的洗葡萄。
但是突然他意识到，每次洗完葡萄，他既不能立刻把洗好的葡萄吃掉（跌份！），又不能丢到垃圾桶（费钱！），只能把葡萄重新放回盘里（绅士~）。
水流激荡，葡萄来回，很快当LR拿起一颗葡萄的时候，洗过的葡萄和没洗过的葡萄已经和高考题里的小球一样在外形、手感和气味上没有任何不同了。
然而处女座的LR是一个非常追求完美的人，LR绝对不能忍受一颗没有洗过的葡萄进入他的唇齿。随意的捡起葡萄并且清洗的LR，望着泊泊的水流陷入了沉思……这样洗葡萄，什么时候才能到自己放心吃的程度啊……
好在我们的LR是一个不容易被难题击倒的人（！），他立刻站在洗漱间展开沉思。
滚滚流出的水流配合着他的思考，十分契合。LR想，我至少要洗这些葡萄个数个葡萄吧。
于是，LR用眼逐一数出葡萄的个数是74个。那么，假如给这些葡萄一一编号，那么LR洗74次恰好洗完的概率是多少呢？他洗过的葡萄的编号必须是1到74的一个排列（也就是74个数排顺序），而每次他洗葡萄的选择都有74种，这样看来，他恰好在74次洗完的概率就是他能够在74次之内洗完的方法数除以他所有可能洗葡萄的方法数，也就是：
嗯…大概…1.57乘以10的-31次方…
嗯…大概比LR本科脱单的概率还要低几个数量级……
于是LR被迫开始考虑，运用这种每次随机拿起一个葡萄清洗的方法，他在统计意义下想要把葡萄接近洗完，需要洗多少次呢？
（水已经放满了托盘开始溢出到外面，
但是陷入沉思的LR显然不会在意这些琐事）
LR意识到他需要首先对这个问题建模（虽然是很sb的模）。那就是，他每次会等概率随机选择一个1到n之间的数字，对这个数字做标记，每次选择的新标记数字和之前选择的数字完全独立。m次标记过程之后，设被标记的数字个数的期望函数E(m)，问题就是求使得E(m)LR满意的个数的最小的m。
完成建模之后的LR十分开心，根本不管还在水龙头下不停翻滚的葡萄，冲进寝室，开始进行思考，毕竟这事关LR到底要洗多少次葡萄啊：
假定这里的n就是74。E(1)的结果十分显然，那就是1。因为第一次你拿起的葡萄一定是没洗过的。E(2)呢？似乎很接近2，但是比2要小一点。因为可能就这么寸，第二次你恰巧就捡起了之前刚刚洗过的那个葡萄，这个概率是1/74。于是，1/74的概率你依然在第二次只洗过了一个葡萄，73/74的概率是两个，于是第二次你洗的葡萄的个数的期望是
那第三次呢？好像很大的概率你还是可以洗到第三个新的没洗过的葡萄的，毕竟没有洗过的葡萄还有那么多。
但是情况稍微有些复杂，1/74的概率前两次你一共只洗了一个葡萄，在这个情况下，你依然是73/74的概率（总概率1/74*73/74）拿起第二个新的葡萄洗，1/74的概率还是拿起了那个被你洗过两遍的可怜葡萄
（葡萄OS：我有一句……）
而在73/74的概率下你前两次洗了两个葡萄，在这个情况下，你有72/74的概率洗干净第三个新葡萄，2/74的概率重新拿起了前两次洗的两个葡萄当中的某个。这样的话，第三次洗过的葡萄总数的期望是
数字已经开始复杂的有些颤抖了，LR不禁吸了一口冷气，外面的葡萄还在盘中因为水流的撞击发出叮当的声音。LR感到他必须要立刻推出一般的情况才可以。
假设有一个数表a，第i行第j列表示第i次洗过之后一共有j个葡萄被洗过的概率，我们注意到只有当j不超过i时才可能是正的（你试试每次洗一个葡萄，洗过两次之后洗完了三个？）我们可以这样推导这个数表的递推式：
在第i+1次清洗时，你面前的一堆葡萄洗过的次数其实处于一种概率的叠加态，洗过第i+1次之后如果存在一共有j个被洗过（概率为a_{i+1,j}）的情况，它只能从第i次早已有j个清洗完成然后你做了一次无用功、或者是第i次只有j-1个被清洗然后你成功洗了一个新的葡萄得来。从前者来概率乘以j/n（也即你随机选到的是已经洗过的j个之一），后者是(n-j+1)/n,所以有递推式
/p>
有了递推式就有了一切！LR迫不及待的敲了程序模拟了这个过程，在设置到底洗到平均意义下多少个葡萄洗过可以使他满意时，他设置了73.99，然后等程序默默运行……
（非coder可以无视，coder可以帮忙Debug）
程序运行了一会结果就出来了……
嗯……即使是在精度出现问题，结果的次数通常偏小的情况下，这个次数，也真是令人满意呢……
LR真是眉头紧锁，为了吃个葡萄，他居然要洗一千多次。这世道实在是让人没法过了啊……
室友看洗漱间一直有葡萄在水中翻滚却无人过问，过来找LR询问情况。
“呜呜呜，我居然要洗一千多次葡萄……”
？？？……………
在听完LR一番精美的理论之后，室友甩给LR第二个托盘。
“把洗好的都放进去，期望铁定是N。”
漫士呓语，欢迎
