\[\begin{aligned} ANS&=\sum_{i=1}^n\binom{n}{i}p^i(1-p)^{n-i}\left(\sum_{j=1}^ij^m\right)& p=\frac{a}{b}\\ &=\sum_{j=1}^nj^m\sum_{i=j}^n\binom{n}{i}p^i(1-p)^{n-i}\\ &=\sum_{j=1}^n\sum_{k=0}^m{m\brace k}\binom{j}{k}k!\sum_{i=j}^n\binom{n}{i}p^i(1-p)^{n-i}\\ &=\sum_{k=0}^m{m\brace k}k!\sum_{i=k}^n\binom{n}{i}p^i(1-p)^{n-i}\sum_{j=k}^i \binom{j}{k}\\ &=\sum_{k=0}^m{m\brace k}k!\sum_{i=k}^n\binom{n}{i}p^i(1-p)^{n-i}\left(\binom{i}{k+1}+\binom{i}{k}\right)\\ &=\sum_{k=0}^m{m\brace k}k!\sum_{i=k}^n\left(\binom{n}{k}\binom{n-k}{i-k}+\binom{n}{k+1}\binom{n-k-1}{i-k-1}\right)p^i(1-p)^{n-i}\\ &=\sum_{k=0}^m{m\brace k}k!\left(\binom{n}{k}\sum_{i=0}^{n-k}\binom{n-k}{i}p^{i+k}(1-p)^{n-k-i}+\binom{n}{k+1}\sum_{i=0}^{n-k-1}\binom{n-k-1}{i}p^{i+k+1}(1-p)^{n-k-1-i}\right)\\ &=\sum_{k=0}^m{m\brace k}k!\left(\binom{n}{k}p^{k}+\binom{n}{k+1}p^{k+1}\right) \end{aligned} \]
只需计算第二类斯特林数的第 \(m\) 行。NTT 即可，复杂度 \(O(m\log m)\)。
没有一个队员是 rdfz 学生的 rdfz 队（cftm,dwt,云浅）ak 了/kx
