写出答案的式子 ∑ i f ( i ) [ ( n − i m ) 2 − ( n − i − 1 m ) 2 ] \sum_{i}^{}f(i)\Big[\binom{n-i}{m}^2-\binom{n-i-1}{m}^2\Big] i∑f(i)[(mn−i)2−(mn−i−1)2] 是关于 n n n 的 3 m + 1 3m+1 3m+1 次多项式，我们需要知道各个点值 利用 f ( k ) = ∑ i f ( i ) ∏ j ≠ i i − j k − j = ∑ i f ( i ) ( m − i ) ! i ! ( − 1 ) m − i k m + 1 ‾ 1 k − i f(k)=\sum_if(i)\prod_{j\neq i}\frac{i-j}{k-j}=\sum_if(i)(m-i)!i!(-1)^{m-i}k^{\underline {m+1}}\frac{1}{k-i} f(k)=i∑f(i)j=i∏k−ji−j=i∑f(i)(m−i)!i!(−1)m−ikm+1k−i1 容易发现是一个卷积
不过我们要优雅地求和 考虑算 x 1 x^1 x1 的期望时的组合意义，即拆为 ∑ 1 \sum 1 ∑1，这等价于我们再放一个求进去
∑ k = m 2 m ( n k + 1 ) ( k m ) ( m 2 m − k ) \sum_{k=m}^{2m}\binom{n}{k+1}\binom{k}{m}\binom{m}{2m-k} k=m∑2m(k+1n)(mk)(2m−km) 然后考虑多放 t t t 个带标号的球进去，容易发现其意义就是 ( ∑ 1 t ) t ! \binom{\sum 1}{t}t! (t∑1)t! 所以 ∑ i i t ‾ [ ( n − i m ) 2 − ( n − i − 1 m ) 2 ] = ∑ k = m 2 m t ! ( n k + t ) ( k m ) ( m 2 m − k ) \sum_i i^{\underline t}\Big[\binom{n-i}{m}^2-\binom{n-i-1}{m}^2\Big]\\=\sum_{k=m}^{2m}t!\binom{n}{k+t}\binom{k}{m}\binom{m}{2m-k} i∑it[(mn−i)2−(mn−i−1)2]=k=m∑2mt!(k+tn)(mk)(2m−km) 我们先转下降幂 ∑ t c t t ! ∑ k = m 2 m ( n k + t ) ( k m ) ( m 2 m − k ) \sum_{t}c_tt!\sum_{k=m}^{2m}\binom{n}{k+t}\binom{k}{m}\binom{m}{2m-k} t∑ctt!k=m∑2m(k+tn)(mk)(2m−km) 容易发现是一个卷积
