CF768D Jon and Orbs

题目简述

有 $k$ 种物品，每次可以取一个物品但是不知道取的是哪种。求把所有种类物品都取遍的概率不小于 $\frac{p}{2000}$ 的最小天数。

思路

方程还是比较好推的，设 $f_{i,j}$ 表示第 $i$ 天时取了 $j$ 种物品的概率，对于第 $i$ 天当天有没有取一种新的物品分类讨论有 $\large f_{i,j}=f_{i-1,j-1}·\frac{k-j+1}{k}+f_{i-1,j}·\frac{j}{k}$；显然第一维可以压掉，要注意倒序。

但是有个问题在于状态里面设了天数但是题中没有给出具体的天数限制 —— 我一开始压掉天数，转移一次判断一次但是 TLE 了。

考虑一下期望的天数，我们知道对于概率为 $p$ 的事件期望 $\frac{1}{p}$ 次实验后会发生，类似上面分类讨论中取到新物品的概率，可以得到所有种类物品都取到的期望天数是 $\Large \Sigma_{i=1}^{k} \frac{k}{k-i+1}$。这个天数是 $k·H_k$ 级别，大概是 $O(k·\ln k)$ 级别的，天数开 8000 就可以过。于是只要提前预处理一下，查询的时候就可以节省时间了。

Code

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<climits>
#define int long long
using namespace std;
const int MaxN = 1003, ln = MaxN*8;
int k, q;
double f[MaxN], g[ln];

inline int Read(){
	int num = 0, op = 1;
	char ch = getchar();
	while(!isdigit(ch)){
		if(ch == '-') op = -1;
		ch = getchar();
	}
	while(isdigit(ch)){
		num = num * 10 + ch - '0';
		ch = getchar();
	}
	return num * op;
}

inline void Init(){
	f[0] = 1.0;
	for(int i=1; i<ln; i++){
		for(int j=k; j>=1; j--){
			f[j] = (f[j-1] * (k-j+1) + f[j] * j) / (k * 1.0);
		}
		g[i] = f[k];
		f[0] = 0;
	}
	return;	
}

signed main(){
	k = Read(), q = Read();
	Init();
	while(q--){
		double p;
		scanf("%lf", &p);
		p /= 2000;
		for(int i=1; i<ln; i++){
			if(g[i] >= p){
				printf("%lld\n", i);
				break;
			}
		}
	}
	return 0;
}