P2791 Solution
给你 \(N,M,S,L\)，\(S\) 组询问，每次给出 \(n,m,k\)，表示有 \(m\) 个 \(1\) 和 \(n-m\) 个 \(0\)，求随机选出 \(k\) 个数的和的 \(L\) 次幂的期望，模数 \(998244353\)。
\(S\le200,L\le2\times 10^5,M\le N\le2\times10^7\)，每次询问的 \(n,m,k\) 满足 \(m,k\le n\le N,m\le M\)。
（题意来自 SSerWarriors_Cat的题解 qwq）
期望等于方案和除以方案数，方案数显然是 \(\dbinom n k\)，那么只需要求方案和。
假设我们从 \(m\) 个 \(1\) 中选出了 \(x\) 个 \(1\)，那么同时我们也要从 \(n-m\) 个 \(0\) 里选 \(k-x\) 个 \(0\)，所以这部分的贡献为 \(\dbinom m x\dbinom{n-m}{k-x}x^L\)。
因此方案和就等于 \(\displaystyle\sum_{i=1}^k\binom m i\binom{n-m}{k-i}i^L\)。
\[\begin{aligned} \sum_{i=1}^k\binom m i\binom{n-m}{k-i}i^L &=\sum_{i=1}^k\binom m i\binom{n-m}{k-i}\sum_{j=1}^i{L\brace j}\binom i jj!\\ &=\sum_{j=1}^k\sum_{i=j}^k\binom m i\binom{n-m}{k-i}{L\brace j}\binom i jj!\\ &=\sum_{j=1}^k{L\brace j}j!\sum_{i=j}^k\binom m i\binom{n-m}{k-i}\binom i j\\ &=\sum_{j=1}^k{L\brace j}j!\sum_{i=j}^k\binom{n-m}{k-i}\frac{m!}{i!(m-i)!}\frac{i!}{j!(i-j)!}\\ &=\sum_{j=1}^k{L\brace j}j!\sum_{i=j}^k\binom{n-m}{k-i}\frac{m!(m-j)!}{(m-i)!j!(i-j)!(m-j)!}\\ &=\sum_{j=1}^k{L\brace j}j!\sum_{i=j}^k\binom{n-m}{k-i}\binom m j\binom{m-j}{i-j}\\ &=\sum_{j=1}^k{L\brace j}j!\binom m j\sum_{i=0}^{k-j}\binom{n-m}{k-i-j}\binom{m-j}{i}\\ \end{aligned}\]对于后面这个部分，我们有范德蒙德卷积：\(\displaystyle\sum_{i=0}^k\binom n i\binom m{k-i}=\binom{n+m}k\)。
这个从组合数的意义证明即可：两堆物品分别有 \(n,m\) 根，枚举从第一堆拿走的物品数，全部加起来相当于从 \(n+m\) 个物品中拿走 \(k\) 个。
则：
\(\displaystyle\sum_{i=1}^k\binom m i\binom{n-m}{k-i}i^L=\sum_{j=1}^k{L\brace j}j!\binom m j\binom{n-j}{k-j}\)
其中 \(\displaystyle{L\brace j}\) 就是【模板】多项式乘法，一遍卷积后再 \(\mathcal O(L)\) 计算即可。
标签：le,frac,p2791,solution,displaystyle,binom,brace,sum From： https://www.cnblogs.com/iorit/p/18046096