题目链接：http://codeforces.com/problemset/problem/768/D
令$f[i][j]$表示当前产生过了$i$个球，产生过了$j$个不同的球的概率。
${Ans_i=Min\left \{ x|f[x][k]>\frac{p_i-\varepsilon }{2000} \right \}}$
考虑转移：
${f[i][j]=\frac{j}{k}*f[i-1][j]+\frac{k-j+1}{k}*f[i-1][j-1]}$
${f[0][0]=1}$
可能答案并不一定小于$K$所以我把$i$的上界设为了${k*10}$
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstdlib>
#include<cmath>
#include<cstring>
using namespace std;
#define maxn 2100
#define llg int
#define UP 10000000
#define eps (double)(1e-7)
#define yyj(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);
llg n,T,m,l,r,mid,ans;
double f[maxn*][maxn],p;
int main()
{
// yyj("D");
cin>>n>>T;
//double N=n;
f[][]=;
for (llg i=;i<=n*;i++)
for (llg j=;j<=n;j++)
f[i][j]=((double)((double)j/n))*f[i-][j]+(double)((double)(n-j+)/n)*f[i-][j-];
while (T--)
{
scanf("%lf",&p);
p=p-eps; p/=; //llg ans;
l=; r=n*;
while (l<=r)
{
mid=(l+r)>>;
if (f[mid][n]>=p){ans=mid; r=mid-;}else l=mid+;
}
printf("%d\n",ans);
}
return ;
}