幼儿园篮球题
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
传送门
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
思路
不难发现，我们要求的答案实际上是这个东西:
∑i=0kiL(mi)(n−mk−i)(nk)\frac{\sum_{i=0}^{k} i^{L}\left(\begin{array}{c} m \\ i \end{array}\right)\left(\begin{array}{c} n-m \\ k-i \end{array}\right)}{\left(\begin{array}{l} n \\ k \end{array}\right)} (nk )∑i=0k iL(mi )(n−mk−i )
于是，我们只需求到分子即可。我们开始愉快的化式子了。
∑i=0kiL(mi)(n−mk−i)\sum_{i=0}^{k} i^{L}\left(\begin{array}{c} m \\ i \end{array}\right)\left(\begin{array}{c} n-m \\ k-i \end{array}\right) i=0∑k iL(mi )(n−mk−i )
我们发现里面难搞的其实是 iLi^{L}iL ，但是我们又有式子:
nm=∑i=0n(ni)i!{mi}n^{m}=\sum_{i=0}^{n}\left(\begin{array}{c} n \\ i \end{array}\right) i !\left\{\begin{array}{c} m \\ i \end{array}\right\} nm=i=0∑n (ni )i!{mi }
对于这个式子的感性证明就是：假设我们现在有 mmm 个小球，要放进 nnn 个盒子里面，没有限制，显然它等于 nmn^{m}nm 。但是，我们还有一种求法，即，我们选出 iii 个盒子放 mmm 个小球，显然要选出 iii 个盒子，然后把 mmm 个小球塞进去，又因为盒子不同，所以还要乘上 iii 。
将上式代入式子中，可以得到:
=∑i=0k(mi)(n−mk−i)∑j=0i(ij)j!{Lj}=\sum_{i=0}^{k}\left(\begin{array}{c} m \\ i \end{array}\right)\left(\begin{array}{c} n-m \\ k-i \end{array}\right) \sum_{j=0}^{i}\left(\begin{array}{l} i \\ j \end{array}\right) j !\left\{\begin{array}{l} L \\ j \end{array}\right\} =i=0∑k (mi )(n−mk−i )j=0∑i (ij
)j!{Lj }
又因为
(mi)(ij)=(mj)(m−ji−j)\left(\begin{array}{c} m \\ i \end{array}\right)\left(\begin{array}{l} i \\ j \end{array}\right)=\left(\begin{array}{c} m \\ j \end{array}\right)\left(\begin{array}{c} m-j \\ i-j \end{array}\right) (mi )(ij )=(mj )(m−ji−j )
这个式子展开之后易证。
所以原式等于:
=∑j=0k{Lj}j!(mj)∑i=jk(m−ji−j)(n−mk−i)=∑j=0k{Lj}j!(mj)∑i=0k−j(m−ji)(n−mk−i−j)\begin{array}{l} =\sum_{j=0}^{k}\left\{\begin{array}{l} L \\ j \end{array}\right\} j !\left(\begin{array}{c} m \\ j \end{array}\right) \sum_{i=j}^{k}\left(\begin{array}{c} m-j \\ i-j \end{array}\right)\left(\begin{array}{c}
n-m \\ k-i \end{array}\right) \\ =\sum_{j=0}^{k}\left\{\begin{array}{l} L \\ j \end{array}\right\} j !\left(\begin{array}{c} m \\ j \end{array}\right) \sum_{i=0}^{k-j}\left(\begin{array}{c} m-j \\ i \end{array}\right)\left(\begin{array}{c} n-m \\ k-i-j \end{array}\right) \end{array} =∑j=0k {Lj
}j!(mj )∑i=jk (m−ji−j )(n−mk−i )=∑j=0k {Lj }j!(mj )∑i=0k−j (m−ji )(n−mk−i−j )
然后你发现后面那个式子是范德蒙德卷积，就等于:
(n−jk−j)\left(\begin{array}{l} n-j \\ k-j \end{array}\right) (n−jk−j )
所以原式等于:
=∑j=0k{Lj}j!(mj)(n−jk−j)=\sum_{j=0}^{k}\left\{\begin{array}{c} L \\ j \end{array}\right\} j !\left(\begin{array}{c} m \\ j \end{array}\right)\left(\begin{array}{l} n-j \\ k-j \end{array}\right) =j=0∑k {Lj }j!(mj )(n−jk−j )
又因为上面提到的 nm=∑i=0n(ni)i!{mi}n^{m}=\sum_{i=0}^{n}\left(\begin{array}{c}n \\ i\end{array}\right) i !\left\{\begin{array}{c}m \\ i\end{array}\right\}nm=∑i=0n (ni )i!{mi }, 这个东西我们可以使用二项式反演得到:
{mn}=∑i=0nimi!(−1)n−i(n−i)!\left\{\begin{array}{l} m \\ n \end{array}\right\}=\sum_{i=0}^{n} \frac{i^{m}}{i !} \frac{(-1)^{n-i}}{(n-i) !} {mn }=i=0∑n i!im (n−i)!(−1)n−i
然后你就发现这是个卷积形式，于是我们就可以 Θ(LlogL)\Theta(L \log L)Θ(LlogL) 预处理出 {Lj}\left\{\begin{array}{l}L \\ j\end{array}\right\}{Lj } 。
不过因为这道题十分卡常，所以我们还需要再化一下式子。
ans =∑j=0k{Lj}j!(mj)(n−jk−j)(nk)=(∑j=0k{Lj}j!m!j!(m−j)!(n−j)!(k−j)!(n−k)!)k!(n−k)!n!=(∑j=0k{Lj}(n−j)!(m−j)!(k−j)!)k!m!n!\begin{array}{c} \text { ans }=\frac{\sum_{j=0}^{k}\left\{\begin{array}{l} L \\ j \end{array}\right\} j !\left(\begin{array}{c} m \\ j \end{array}\right)\left(\begin{array}{c} n-j
\\ k-j \end{array}\right)}{\left(\begin{array}{l} n \\ k \end{array}\right)} \\ =\left(\sum_{j=0}^{k}\left\{\begin{array}{l} L \\ j \end{array}\right\} j ! \frac{m !}{j !(m-j) !} \frac{(n-j) !}{(k-j) !(n-k) !}\right) \frac{k !(n-k) !}{n !} \\ =\left(\sum_{j=0}^{k}\left\{\begin{array}{l} L \\ j
\end{array}\right\} \frac{(n-j) !}{(m-j) !(k-j) !}\right) \frac{k ! m !}{n !} \end{array} ans =(nk )∑j=0k {Lj }j!(mj )(n−jk−j ) =(∑j=0k {Lj }j!j!(m−j)!m! (k−j)!(n−k)!(n−j)! )n!k!(n−k)! =(∑j=0k {Lj }(m−j)!(k−j)!(n−j)! )n!k!m!
我们又发现上界其实是 min{n,k,L}\min \{n, k, L\}min{n,k,L} ，所以至此，我们可以 Θ(LlogL+SL)\Theta(L \log L+S L)Θ(LlogL+SL) 解决此题目。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
CODECODECODE
