题解 CF1278F 【Cards】
yijan
·
·
题解
CF1278F Cards
我也不知道公式挂没有，还是建议在 luogu 博客或者下面的链接里面查看。
一道斯特林数的模版练手题。不会可以看 这里 。
我们考虑枚举出现了多少次王牌，出现 i 次王牌的概率，可以从 n 轮操作选择 i 轮抽出王牌，写成式子：
\begin{aligned}& \sum_{i\ge 0} i^k{n\choose i}\frac 1 m^{i} \frac{m-1}{m}^{n-i}\\&= \frac{1}{m^n} \sum_{i= 0}^n i^k {n\choose i} (m-1)^{n-i}\\&= \frac 1 {m^n} \sum_{i=0}^n {n\choose i} (m-1)^{n-i} \sum_{j=0}^k \left\{\begin{array}{l} k \\ j \end{array}\right\} i^{\underline j}\\&= \frac 1 {m^n} \sum_{i=0}^n {n\choose i} (m-1)^{n-i} \sum_{j=0}^k \left\{\begin{array}{l} k \\ j \end{array}\right\} {i\choose j}j!\\&= \frac 1 {m^n} \sum_{j=0}^k \left\{\begin{array}{l} k \\ j \end{array}\right\} j! \sum_{i=0}^n {n\choose i} {i\choose j} (m-1)^{n-i}\\&= \frac 1 {m^n} \sum_{j=0}^k \left\{\begin{array}{l} k \\ j \end{array}\right\} j! {n\choose j}\sum_{i=0}^n {n-j\choose i-j} (m-1)^{n-i}\\\end{aligned}
最后一步用到了以前写过的那个组合恒等式，就是从 n 个选 i 个再选 j 个，本质上等价于 n 个先选择好 j 个，再从剩下的 n-j 个选择第一步应当选择的 i-j 个。
然后可以看出最后面其实是个二项式定理！
= \frac 1 {m^n} \sum_{j=0}^k \left\{\begin{array}{l} k \\ j \end{array}\right\} j! {n\choose j}m^{n-j}
然后可以很简便地写 O(k^2) 了，也可以预处理第二类斯特林数的行 O(k\log k) 做。可以去看 这里 的题解。