CF1156F. Card Bag

Solution

概率$DP$。
記$cn{t}_i$表示有多少個$a_j=i$，再把$a_i$離散化。
令$f_{i,j}$表示當(dāng)前取過$i$個數(shù)，當(dāng)前取到了$a_j$的概率。
$$f_{i,j}=f_{i?1,k}?\frac{cn{t}_{a_i}}{n?i+1}$$
$$Ans=\sum f_{i,j}?\frac{cn{t}_{a_i}?1}{n?i}$$
轉(zhuǎn)移用前綴和優(yōu)化即可。
時間復(fù)雜度$O(n^2)$

總結(jié)

以上是生活随笔為你收集整理的CF1156F. Card Bag的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。