P4550 收集邮票 赠券收集问题升级版 【期望，推公式】

https://www.luogu.com.cn/problem/P4550

计算次数的期望部分

E[i] : 表示当前已经取得了i，再之后还需要E[i]次才能获得所有
转移方程E[i] = i/N * E[i] + (N-i)/N * E[i+1] + 1
做出一种转移，就需要消耗一次，所以+1
E[i] = E[i+1] + N/(N-i),E[N] = 0

计算花钱的期望部分

f[i]: 表示当前已经取得了i，在之后还需要f[i]钱才能获得所有
转移方程：f[i] = i/N * (f[i] + E[i] + 1) + (N-i)/N * (f[i+1] + E[i+1] + 1)
E[i] + 1:表示本次选择的是已经获得过的那i种，之后还需要的钱数，因为需要多少次就需要多少钱，E[i]+1就是需要多少次
E[i+1]+1 同理

#include <stdio.h>
#include <cstring>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <iostream>
#include <map>

#define go(i, l, r) for(int i = (l), i##end = (int)(r); i <= i##end; ++i)
#define god(i, r, l) for(int i = (r), i##end = (int)(l); i >= i##end; --i)
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug_in  freopen("in.txt","r",stdin)
#define debug_out freopen("out.txt","w",stdout);
#define pb push_back
#define all(x) x.begin(),x.end()
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pii;
const ll maxn = 1e4+10;
const ll maxM = 1e6+10;
const ll inf_int = 1e8;
const ll inf_ll = 1e17;

template<class T>void read(T &x){
    T s=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    x = s*w;
}
template<class H, class... T> void read(H& h, T&... t) {
    read(h);
    read(t...);
}

void pt(){ cout<<'\n';}
template<class H, class ... T> void pt(H h,T... t){ cout<<" "<<h; pt(t...);}

//--------------------------------------------
int N;
double E[maxn],f[maxn];
int main() {
//    debug_in;
//    debug_out;

    read(N);
    //计算E[i]
    for(int i = N-1;i>=0;i--){
        E[i] = E[i+1] + (double)N/(N-i);
    }
    //计算f[i]
    for(int i = N-1;i>=0;i--){
        f[i] = (double)N/(N-i) * ( (double)i/N * (E[i] + 1) + (double)(N-i)/N *(f[i+1] + E[i+1] + 1));
    }
    printf("%.2f\n",f[0]);


    return 0;
}