Dice (III)

Given a dice with n sides, you have to find the expected number of times you have to throw that dice to see all its faces at least once. Assume that the dice is fair, that means when you throw the dice, the probability of occurring any face is equal.

For example, for a fair two sided coin, the result is 3. Because when you first throw the coin, you will definitely see a new face. If you throw the coin again, the chance of getting the opposite side is 0.5, and the chance of getting the same side is 0.5. So, the result is

1 + (1 + 0.5 * (1 + 0.5 * …))

= 2 + 0.5 + 0.52 + 0.53 + …

= 2 + 1 = 3

Input
Input starts with an integer T (≤ 100), denoting the number of test cases.

Each case starts with a line containing an integer n (1 ≤ n ≤ 105).

Output
For each case, print the case number and the expected number of times you have to throw the dice to see all its faces at least once. Errors less than 10-6 will be ignored.

Sample Input

5
1
2
3
6
100

Sample Output

Case 1: 1
Case 2: 3
Case 3: 5.5
Case 4: 14.7
Case 5: 518.7377517640

题意
n面的骰子，求每个面至少出现一次的投骰子次数的期望

题解
这看了半天也推不出来是个什么式子。
不看题解真想不起来几何分布了。
几何分布
X的概率分布$P(X=k)=(1-p)^{k-1}p\ \ (k=1、2\cdots)$P(X=k)=(1−p)k−1p  (k=1、2⋯)
X表示在无限次伯努利试验中,事件A第一次发生的概率。则P(X)满足参数为p的几何分布
几何分布的期望为$E(X)=\cfrac{1}{p}$E(X)=p1​
所以第一个面出现的概率$\cfrac{n}{n}$nn​
第二个面第一次出现的概率$\cfrac{n-1}{n}$nn−1​
第i个面第一次出现的概率$\cfrac{n-i+1}{n}$nn−i+1​
$\cdots$⋯
故每个面至少出现一次的期望$E(X)=\displaystyle\sum_{i=1}^{n}1·P_i=\displaystyle\sum_{i=1}^{n}\cfrac{n}{n-i+1}$E(X)=i=1∑n​1⋅Pi​=i=1∑n​n−i+1n​

代码

#include <bits/stdc++.h>

using namespace std;
#define me(x,y) memset(x,y,sizeof x)
#define MIN(x,y) x < y ? x : y
#define MAX(x,y) x > y ? x : y

typedef long long ll;
typedef unsigned long long ull;

const int maxn = 1e5+10;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9+7;
const double eps = 1e-09;
const double PI = acos(-1.0);



int main(){
    int t,ca=1;cin>>t;
    while(t--){
        int n;scanf("%d",&n);
        double ans=0;
        for(int i = 1; i <= n; ++i){
            ans += 1.0*n/i;
        }
        printf("Case %d: %.10f\n",ca++,ans);
    }
    return 0;
}