https://www.luogu.com.cn/problem/P2791
卡时间卡空间的duliu题（
但NMSL好评
考虑一次询问\(n,m,k\)，由于是随机选的球，所以期望就是所有方案的权值和 / 方案数
枚举有多少没气的
\[\frac{1}{\binom{n}{k}}\sum\limits_{i=0}^k \binom{m}{i}\binom{n-m}{k-i} i^L
\]
跑掉前面那个不管，我们来看后面
有个\(i^L\)我算个啥啊，把那玩意儿用第二类斯特林数展开
\[\begin{aligned} &\quad \sum\limits_{i=0}^k \binom{m}{i} \binom{n-m}{k-i} i^L \\ &= \sum\limits_{i=0}^{k} \binom{m}{i} \binom{n-m}{k-i} \sum\limits_{j=0}^{i} \binom{i}{j} \begin{Bmatrix} L \\ j \end{Bmatrix} j! \\ &= \sum\limits_{j=0}^k \begin{Bmatrix}L \\ j\end{Bmatrix}j! \sum\limits_{i=j}^{k} \binom{m}{i}\binom{i}{j} \binom{n-m}{k-i} \\ &= \sum\limits_{j=0}^{k} \begin{Bmatrix}L \\ j\end{Bmatrix}j!\sum\limits_{i=j}^k \binom{m}{j}\binom{m-j}{i-j}\binom{n-m}{k-i} \\ &= \sum\limits_{j=0}^{k} \binom{m}{j}\begin{Bmatrix}L \\ j\end{Bmatrix}j!\sum\limits_{i=j}^k\binom{m-j}{i-j}\binom{n-m}{k-i} \\ &= \sum\limits_{j=0}^{k} \binom{m}{j}\begin{Bmatrix}L \\ j\end{Bmatrix}j!\sum\limits_{i=0}^{k-j}\binom{m-j}{i}\binom{n-m}{k-i-j} \end{aligned}
\]
然后后面是一个范德蒙德卷积）
大概长这样
\[\sum\limits_{i=0}^n \binom{a}{i}\binom{b}{n-i} = \binom{a+b}{n}
\]
感性理解一下就是两坨东西，各有\(a,b\)个，然后枚举第一堆里选\(i\)个第二堆里选\(n-i\)个，共选\(n\)个出来，就是\(C(a+b,n)\)
所以
\[\begin{aligned}&\quad \sum\limits_{j=0}^{k} \binom{m}{j}\begin{Bmatrix}L \\ j\end{Bmatrix}j!\sum\limits_{i=0}^{k-j}\binom{m-j}{i}\binom{n-m}{k-i-j} \\ &= \sum\limits_{j=0}^{k} \binom{m}{j}\begin{Bmatrix}L \\ j\end{Bmatrix}j!\binom{n-j}{k-j} \\ &= \sum\limits_{j=0}^{k} \binom{m}{j}\begin{Bmatrix}L \\ j\end{Bmatrix}j!\binom{n-j}{n-k}\end{aligned}
\]
实际上\(j\)只需要跑到\(\min \{L,m,k\}\)（\(m \le n\)）
于是FFT求出第\(L\)行的第二类斯特林数，枚举\(j\)累加答案
但是
这duliu出题人卡了时间
众所周知，取模特别特别的慢，所以我们考虑给组合数约分，即
\[Ans = \frac{k!(n-k)!}{n!}\sum\limits_{j=0}^{L} \frac{m!}{j!(m-j)!}\begin{Bmatrix}L \\ j\end{Bmatrix}j!\frac{(n-j)!}{(n-k)!(k-j)!}
\]
先约分，然后把与\(j\)无关的提到外面，可以得到
\[Ans = \frac{k!m!}{n!} \sum\limits_{j=0}^{L} \frac{(n-j)!}{(m-j)!(k-j)!}\begin{Bmatrix}L \\ j\end{Bmatrix}
\]
大大减少了做乘法和取模的次数）
还有就是在求逆元的时候，用乘法逆元2的方法，可以减少取模次数
然后在求第二类斯特林数的时候那个\(L\)次幂可以线性筛预处理出来
这样应该能卡过去了，Code
[题解] LuoguP2791 幼儿园篮球题
原文：https://www.cnblogs.com/wxq1229/p/13295132.html
