题目就是求第K种原料的出现期望时间。
考虑广义min-max容斥。
\(\text{kthmax}(S)=\sum\limits_{T\subseteq S}(-1)^{|T|-k}\binom{|T|-1}{k-1}\min(T)\)
显然\(\min(T)=\frac{m}{\sum\limits_{i\in S}p_i}\)。
发现\(m\)的范围很小，那么我们可以考虑设状态dp算贡献。
设\(f_{j,k}\)表示对于集合\(|S|\)，\(j=\sum\limits_{i\in S}p_i\)，集合大小为\(k\)的方案数。
转移显然。
但是时间复杂度为\(O(n^2m)\)，难以ac。
观察到还有\(|n-k|<=10\)的条件，考虑改变状态。
设\(f_{j,k}\)表示对于集合\(S\)，\(j=\sum\limits_{i\in S}p_i\)，
组合数下标为\(k\)的\(\sum\limits_{T}(-1)^{|T|-k}\binom{|T|-1}{k-1}\min(T)\)的值。
对于一个概率为\(v\)的新物品：
如果不加入，直接累加前面的答案。
如果加入，那么答案应该是从\(f_{j-v,k-1}\)转移过来。
我们观察一波式子(标解)
我们用\(g_{i,j}\)表示对于集合\(S\)，\(|S|=i\)，\(j= \sum\limits_{k\in S}p_k\)的方案数。
对于\(f_{j-v,k}\)：
\(f_{j-v,k-1}=\sum\limits_{i}(-1)^{i-k+1}\binom{i-1}{k-2}g_{i,j-v}\)
\(=-\sum\limits_{i}(-1)^{i-k}\binom{i-1}{k-2}g_{i,j-v}\)
增加一个物品后：
\(\triangle f_{j,k}=\sum\limits_i(-1)^{i-k+1}\binom{i}{k-1}g_{i,j-v}\)
\(=-\sum\limits_i(-1)^{i-k}\binom{i}{k-1}g_{i,j-v}\)
两式相减：
\(\triangle f_{j,k}-f_{j-v,k-1}=-\sum\limits_i(-1)^{i-k}\binom{i-1}{k-1}g_{i,j-v}\)
\(=-f_{j-v,k}\)
因此我们得到了递推式：
\(f_{j,k}=f'_{j,k}+f'_{j-v,k-1}-f'_{j-v,k}\)
因此我们就可以\(O(m*(n-k))\)解决dp。
答案就是\(\sum\limits_{i=1}^{m}\frac{m}{i}f_{i,k}\)
原文：https://www.cnblogs.com/Trrui/p/9994668.html