Day11

设dp_i为已经出现了i面，需要的期望次数，dp_n=0

那么dp_i= i/n*dp_i + (n-i)/n*dp_(i+1) + 1

现在已经i面了，i/n的概率再选择一次i面，(n-i)/n的概率选到新的一面，分别乘其期望次数，并且这次丢过，所以+1

#include<bits/stdc++.h>
using namespace std;
#define lowbit(x) ((x)&(-x))
typedef long long LL;
typedef pair<int,int> pii;

const int maxm = 1e5+5;
double dp[maxm];

void run_case() {
    int n; cin >> n;
    dp[n] = 0;
    for(int i = n-1; i >= 0; --i)
        dp[i] = dp[i+1] + (double)n / (n-i);
    cout << dp[0] << "
";
}
 
int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    cout.flags(ios::fixed);cout.precision(10);
    int t; cin >> t;
    //while(t--)
    for(int i = 1; i <= t; ++i) {
        cout << "Case " << i << ": ";
        run_case();
    }
    cout.flush();
    return 0;
}