[CF768D] Jon and Orbs

Description

(n) 种物品，求一次取一件把所有种类取遍的概率不小于给定值 (p/2000) 的最小天数。

Solution

设 (f[i][j]) 表示前 (i) 次取出了 (j) 种的概率，则

设 (m) 为一足够大的数（不妨取 (10^4)），则对于每个询问，找到最小的 (k) 使得 (f[m][n] ge p/2000) 即可

#include <bits/stdc++.h>
using namespace std;

#define int long long
const int N = 2005;

int n,q,p[N];
double f[N*5][N];

signed main()
{
    ios::sync_with_stdio(false);
    cin>>n>>q;
    for(int i=1;i<=q;i++)
    {
        cin>>p[i];
    }
    f[0][0]=1;
    int m=1e4;
    for(int i=1;i<=m;i++)
    {
        for(int j=1;j<=n;j++)
        {
            f[i][j] = f[i-1][j]*j/n + f[i-1][j-1]*(n-j+1)/n;
        }
    }
    for(int i=1;i<=q;i++)
    {
        int t=1;
        for(int j=1;j<=m;j++)
        {
            if(f[j][n]<p[i]*0.0005) ++t;
        }
        cout<<t<<endl;
    }
}