题解-CF1278

经典组合计数题

每次第一张是王的概率是 \(\frac{1}{m}\)，设为 \(p\)，不是的概率 \(\frac{m-1}{m}\) 设为 \(q\)。那么有 \(a\) 次的概率即为 \([z^a](pz+q)^n\)。所求即为 \(\sum\limits_{i=0}^{n}\binom{n}{i}p^iq^{n-i}i^k\)。考虑普通幂转组合数，即 \(x^k=\sum\limits_{i=0}^{k}{k\brace i}\binom{x}{i}i!\)。那么可得答案为

\[\begin{aligned} ans&=\sum_{i=0}^{n}\binom{n}{i}p^iq^{n-i}i^k\\ &=\sum_{i=0}^{n}\binom{n}{i}p^iq^{n-i}\sum_{j=0}^{k}{k\brace j}\binom{i}{j}j!\\ &=\sum_{i=0}^{k}{k\brace i}i!\sum_{j=0}^{n}\binom{n}{j}\binom{j}{i}p^jq^{n-j}\\ &=\sum_{i=0}^{k}\binom{n}{i}{k\brace i}i!\sum_{j=0}^{n}\binom{n-i}{n-j}p^jq^{n-j}\\ &=\sum_{i=0}^{k}\binom{n}{i}{k\brace i}i!\sum_{j=0}^{n-i}p^i\binom{n-i}{j}q^{j}p^{n-i-j}\\ &=\sum_{i=0}^{k}\binom{n}{i}{k\brace i}i!p^i(p+q)^{n-i}\\ &=\sum_{i=0}^{k}\binom{n}{i}{k\brace i}i!p^i\\ &=\sum_{i=0}^{\min(k,n)}{k\brace i}p^in^{\underline{i}}\\ \end{aligned} \]

https://codeforces.com/contest/1278/submission/145038975