Description：

有两个袋子，每次从两个袋子中分别取一个球作为 $n$ 和 $m$ ，取 $n$ 的袋子中有 $num_{n_i}$ 个 $n_i$ ，取 $m$ 的袋子中有 $num_{m_i}$ 个 $m_i$ ，取出 $m$ 个球 $n$ 个袋子，将球随机放入袋子中，然后随机找出一个袋子，猜里面的球数为 $x$ ，求 $k$ 阶中心距，即： $E((x-E(x))^k)$ 。

要求复杂度 $O(nk^2)$

Solution：

首先所有的袋子都是相同的，那么我们可以假装选了确定的一个袋子，然后计算这里面球的个数，假如是 $g$ ，由于球的个数的期望是 $\frac m n$ ，所以 $k$ 阶中心距就是 $(g-\frac m n)^k$ ，这个袋子中有 $g$ 个球的方案数是 $C(m,g)\times(n-1)^{m-g}$ 非常直观不用解释，所以假如我们已知 $m$ 和 $n$ ，答案就是： $$ \frac1{n^m}\sum_{g=0}^m\binom m g\times(n-1)^{m-g}\times(g-\frac m n)^k $$ 把后面那个用二项式定理拆开，得到 $g$ 的幂，然后再用第二类斯特林数展开成下降幂： $$ \begin{align} &\frac1{n^m}\sum_{g=0}^m\binom m g\times(n-1)^{m-g}\times(g-\frac m n)^k\\ =&\frac1{n^m}\sum_{g=0}^m\binom m g\times(n-1)^{m-g}\times\sum_{i=0}^k\binom ki(-\frac m n)^{k-i}g^i\\ =&\frac1{n^m}\sum_{g=0}^m\binom m g\times(n-1)^{m-g}\times\sum_{i=0}^k\binom ki(-\frac m n)^{k-i}\sum_{j=0}^iS_2(i,j)g^{\underline j}\\ =&n^{-m}\sum_{i=0}^k\binom ki(-\frac m n)^{k-i}\sum_{j=0}^iS_2(i,j)\sum_{g=0}^m\binom m g\times (n-1)^{m-g}\times g^{\underline j} \end{align} $$ 这时候有一个结论，就是： $$ \sum_{i=0}^m\binom mi(n-1)^{m-i}i^{\underline w}=m^{\underline w}n^{m-w} $$ 证明的话： $$ \begin{align} \sum_{i=0}^m\binom mi(n-1)^{m-i}\binom i ww!&=\binom m ww!n^{m-w}\\ \sum_{i=0}^m\binom m w\binom{m-w}{i-w}(n-1)^{m-i}&=\binom m wn^{m-w}\\ \sum_{i=0}^m\binom{m-w}{i-w}(n-1)^{m-i}&=n^{m-w}\\ \sum_{i=0}^{m-w}\binom{m-w}i(n-1)^{m-w-i}&=n^{m-w} \end{align} $$ 最后一行显然就是二项式定理，这个结论有点类似下降幂的二项式定理。

因此，原式等于： $$ n^{-m}\sum_{i=0}^k\binom ki(-\frac m n)^{k-i}\sum_{j=0}^iS_2(i,j)m^{\underline j}n^{m-j}=\sum_{i=0}^k\binom ki(-\frac m n)^{k-i}\sum_{j=0}^iS_2(i,j)m^{\underline j}n^{-j} $$ 然后再用第一类斯特林数把这个下降幂变回去： $$ \begin{align} &=\sum_{i=0}^k\binom ki(-\frac m n)^{k-i}\sum_{j=0}^iS_2(i,j)\sum_{w=0}^jS_1(j,w)(-1)^{j-w}m^wn^{-j}\\ &=\sum_{i=0}^k(-1)^{k-i}\binom ki\sum_{j=0}^iS_2(i,j)\sum_{w=0}^jS_1(j,w)(-1)^{j-w}m^{w+k-i}n^{-j-k+i}\\ &=\sum_{i=0}^k(-1)^{i}\binom ki\sum_{j=0}^{k-i}S_2(k-i,j)\sum_{w=0}^jS_1(j,w)(-1)^{j-w}m^{w+i}n^{-j-i}\\ &=\sum_{i=0}^k(-1)^{i}\binom ki\sum_{j=0}^{k-i}S_2(k-i,j)n^{-j-i}\sum_{w=0}^jS_1(j,w)(-1)^{j-w}m^{w+i}\\ \end{align} $$ 两个斯特林数 $O(n^2)$ 预处理没有问题，后面那个求和号也可以预处理，然后就可以 $O(N_n^2k+N_mk+N_kk^2)$ 暴力求了。

Code：

代码就不放了