CFR 768 D. Jon and Orbs ( DP, Probability )

Problem - D - Codeforces

題意：
有 K 種卡片，每天都可以抽一張，抽到的種類機率分佈是隨機均勻。Q 筆詢問，問第幾天開始可以確定，對於任意一種卡片，有 P / 2000 的機率有至少一張。

資料規模：
First line consists of two space separated integers k, q (1 ≤ k, q ≤ 1000) — number of different kinds of orbs and number of queries respectively.
Each of the next q lines contain a single integer pi (1 ≤ pi ≤ 1000) — i-th query.
相對誤差允許 < 1e-7

解法：
考慮動態規劃：
dp[ i ][ j ] : 已過 i 天，已有 j 種卡片的機率
轉移很顯然，詳見代碼
至於 i 最大要到幾天，考慮最大的卡片種類數 K = 1000。令這個最大天數為 X，由於任意一天抽不到某一固定種類卡片的機率為 ( 1 - 1 / K )，所以經過 X 天還是抽不到的機率為 ( 1 - 1 / K ) ** X。隨便代 X = 10000 發現誤差可以通過。

時間 / 空間複雜度：
O( 10000 * ( K + Q ) )

K, Q = map( int, input().split() )

dp = [ [ 0.0 for i in range( K + 1 ) ] for j in range( 10000 ) ]
dp[ 0 ][ 0 ] = 1.0
for i in range( 1, 10000, 1 ):
  for j in range( 1, K + 1, 1 ):
    dp[ i ][ j ] = dp[ i - 1 ][ j ] * j / K + dp[ i - 1 ][ j - 1 ] * ( K - ( j - 1 ) ) / K

for qi in range( Q ):
  P = int( input() )
  for i in range( 10000 ):
    if P <= dp[ i ][ K ] * 2000:
      print( i )
      break