牛清楚的裙子_牛客博客

由于每条裙子被选中的概率相同,这点可以认为 $n$ 条裙子没有差异

那么定义 $f[i]$ 为已经穿过 $i$ 条裙子,为了达到终止条件,期望还需要穿几次

$f[i]=\frac{i}{n}f[i]+\frac{n-i}{n}f[i+1]+1$

意思是,选中穿过的裙子概率 $\frac{i}{n}$ ,选中没穿过的 $\frac{n-i}{n}$ ,然后本次也需要穿 $1$ 次裙子

那么化简得到 $f[i]=f[i+1]+\frac{n}{n-i}$

那么 $f[0]=\sum\limits_{i=0}^{n-1}\frac{n}{n-i}$

上面提到每条裙子无差异,可以认为被穿过的次数相等,所以除以一个 $n$

每条裙子期望被穿过 $\frac{1}{1}+\frac{1}{2}+\frac{1}{3}...+\frac{1}{n}$

不难发现这个时候只需要预处理这个调和级数的前缀和就可以 $O(1)$ 知道每条裙子被穿过的期望次数

然后输出答案即可...

其实这是个经典的"邮票收集问题"，知道就很好写啦

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e7 + 5;
double f[maxn];
int main()
{
    for(int i=1;i<=10000000;i++) f[i] = f[i-1] + 1.0/i;
    int T; cin>>T;
    while(T--)
    {
        int n; scanf("%d", &n);
        double ans = (n-1) * f[n] + f[n] * 10000;
        printf("%.7f\n", ans);
    }
}
/*
author:Issue!
*/