Time Limit: 1 Sec Memory Limit: 162 MB
Submit: 546 Solved: 455
[Submit][Status][Discuss]
Description
有n种不同的邮票，皮皮想收集所有种类的邮票。唯一的收集方法是到同学凡凡那里购买，每次只能买一张，并且
买到的邮票究竟是n种邮票中的哪一种是等概率的，概率均为1/n。但是由于凡凡也很喜欢邮票，所以皮皮购买第k
张邮票需要支付k元钱。现在皮皮手中没有邮票，皮皮想知道自己得到所有种类的邮票需要花费的钱数目的期望。
Input
一行,一个数字N N<=10000
Output
要付出多少钱. 保留二位小数
Sample Input
3
Sample Output
21.25
HINT
Source
题解
奥妙重重的概率dp
懒得打详细推到了，思路简单列一列
(g[i])表示现在有(i)张，要买到(n)张的期望次数
(P(x,i))表示买x次能买到第(i+1,i+2,ldots,n)种邮票的概率，有
[g[i]=sum_{x=0}^{infty}x imes P(x,i)
]
考虑下一张，有(frac{i}{n})的概率拿到已有的(i)张的某一种，有(frac{n-i}{n})的概率拿到没有的那(n-i)种，有
[g[i] = g[i+1] imes frac{n-i}{n} + g[i] imes frac{i}{n} + 1
]
化简有
[g[i] = g[i+1] + frac{n}{n-i},g[n] = 0
]
(f[i][j])表示现在有(i)张，下一张(j)元，买到(n)张的期望价钱，转移有：
[f[i][j] = f[i][j+1] imes frac{i}{n}+f[i+1][j+1] imes frac{n-i}{n}+j
]
又有
[f[i][j]=sum_{x=0}^{infty}[j + (j+1) + (j+2) + ldots + (x+j-1)] imes P(x,i)
]
等差数列求和后作差（(f[i][j+1]-f[i][j])），化简得到
[g[i] = f[i][j + 1] - f[i][j]
]
把这个式子带入上面那个(f[i][j] = f[i][j+1] imes frac{i}{n}+f[i+1][j+1] imes frac{n-i}{n}+j)消去(j + 1)变成(j)
化简，会发现跟(j)没关系，把(j)全带成(1)，得到
[f[i] = f[i+1]+g[i+1]+g[i] imes frac{i}{n-i} + frac{n}{n-i}
]