Codeforces 768D(概率DP)

Codeforces 768D
设$dp(i,j)$为前$i$天生产了$j$种不同的水晶的概率，转移方程：
$$dp(i,j)=dp(i-1,j) \times \frac{j}{k} + dp(i-1,j-1) \times \frac{k-j+1}{k}$$
之后判断$dp(i,k)$是否大于给定条件，答案为$i$
然后因为$p<=1000$，所以把所有情况先预处理出来，直接输出即可。
此题可以把第一维压掉，注意$eps=1e-7$不要写作$eps=1e7$

Codeforces Submission

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
const int MAXQ = 1000 + 5;
const db eps = 1e-7;
int now, k, Q, ans[MAXQ];
db dp[MAXQ];
void clean() {
    ms(dp, 0), dp[0] = 1.0, now = 1;
}
void solve() {
    clean();
    for (int i=1;now<=1000;i++) {
        for (int j=k;j>0;j--) dp[j] = (dp[j] * (db)j + dp[j-1] * (db)(k-j+1)) / (db)k;
        while (now <= 1000 && dp[k] * 2000.0 >= (now - eps)) {
            ans[now] = i, now++;
        }
        dp[0] = 0.0;
    }
    for (int i=1;i<=Q;i++) {
        int p;
        scanf("%d", &p);
        printf("%d\n", ans[p]);
    }
}
int main() {
    #ifndef ONLINE_JUDGE 
    freopen("1.in", "r", stdin);freopen("1.out", "w", stdout);
    #endif
    scanf("%d%d", &k, &Q), solve();
    return 0;
}