直接暴力dp就行……f(i,j)表示前i天集齐j种类的可能性。不超过10000天就能满足要求。
#include<cstdio>
using namespace std;
#define EPS 1e-10
int K,q,p;
double f[10010][1010];
int main()
{
// freopen("d.in","r",stdin);
scanf("%d%d",&K,&q);
f[0][0]=1.0;
for(int i=1;i<=10000;++i)
for(int j=1;j<=K && j<=i;++j)
f[i][j]=f[i-1][j]*((double)j/(double)K)+f[i-1][j-1]*((double)(K-(j-1))/(double)K);
for(int i=1;i<=q;++i)
{
scanf("%d",&p);
for(int j=1;j<=10000;++j)
if(f[j][K]-((double)p/2000.0)>(-EPS))
{
printf("%d\n",j);
break;
}
}
return 0;
}