LG4707 重返现世（扩展 min-max 容斥）
题目链接 洛谷 题意简述 有 n n 种颜色，每秒会出现一种颜色，第 i i 种颜色出现概率为 p i m p i m ，其中 m = n ∑ i = 1 p i m = ∑ i = 1 n p i ，求共出现 k k 种颜色的期望用时，对 998244353 998244353 取模。 1 ≤ k ≤ n ≤ 1000 1 ≤ k ≤ n ≤ 1000 ， m ≤ 10000 m ≤ 10000 ， k ≥ n − 10 k ≥ n − 10 。 简要做法 扩展 min-max 容斥 k - t h m a x ( S ) = ∑ T ⊆ S , T ≠ ∅ ( − 1 ) | T | − k ( | T | − 1 k − 1 ) min ( T ) k - t h m a x ( S ) = ∑ T ⊆ S , T ≠ ∅ ( − 1 ) | T | − k ( | T | − 1 k − 1 ) min ( T ) 其中 k - t h m a x ( S ) k - t h m a x ( S ) 表示 S S 这个集合的第 k k 大元素， min ( T ) min ( T ) 表示 T T 这个集合中最小的元素。 证明可以使用二项式反演，不会二项式反演也记不住式子的话，考场现推可以设 k - t h m a x ( S ) = ∑ T ⊆ S , T ≠ ∅ f ( | T | ) min ( T ) k - t h m a x ( S ) = ∑ T ⊆ S , T ≠ ∅ f ( | T | ) min ( T ) 然后算。 这个式子还可以推广到期望，“第 k k 大的期望”意思是 ∑ x ⋅ p ( x = k - t h m a x ( S ) ) ∑ x ⋅ p ( x = k - t h m a x ( S ) ) 。（ p ( e v e n t ) p ( e v e n t ) 表示...