Codeforces 768D：Jon and Orbs

题目链接：

题目大意：共有k种蛋，每天随机孵化其中一个，每次query每种蛋都至少有一个的概率>p_i/2000需要多少天，一共询问q次。

概率dp

定义状态：dp[第i天][已孵化j种蛋]为改装状态下的概率;

状态转移方程：dp[i][j]=[1-(j-1)/k]*dp[i-1][j-1]+(j/k)*dp[i-1][j];

/*需要注意的是dp[i][0]=0，其中i>1*/

我们可以离线处理所有询问（按p_i升序排列），再恢复原排列输出，已达到询问总复杂度O（nlgn），

观察到1≤p_i≤1000，故亦可以保存对应p_i=1 to 1000的ans，达到询问总复杂度O（n）.

代码如下：

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #define N 1005 5 using namespace std; 6 int n,k,q,ans[N],p; 7 double dp[10*N][N]; 8 int main(void){ 9     scanf("%d%d",&n,&q);10     dp[0][0]=1;11     for(int i=1;i<10*N;++i){12         dp[i][0]=0;13         for(int j=1;j<=n;++j)14             dp[i][j]=(dp[i-1][j-1]*(n-j+1)+dp[i-1][j]*j)/n;15     }16     for(int i=1;i<=1000;++i){17         while(dp[k][n]*2000