传送门 to luogu
这玩意儿怎么天天考，问题是我还不会做！
重要等式 n m = ∑ i = 0 m ( n i ) × i ! × S ( m , i ) n^m=\sum_{i=0}^{m}{n\choose i}\times i!\times S(m,i) nm=i=0∑m(in)×i!×S(m,i)
其中 S ( m , i ) S(m,i) S(m,i) 表示 m m m 个不同的球放入 i i i 个相同的盒子（不能空盒）的方案数。
为啥这个东西比较带劲呢？其实就是为了搞出 ( n i ) {n\choose i} (in) 罢了。就可以和前面的组合数互相制约。
于是原题中的式子就可以写成
∑ i = 0 n ( n i ) ∑ j = 0 k ( i j ) × j ! × S ( k , j ) \sum_{i=0}^{n}{n\choose i}\sum_{j=0}^{k}{i\choose j}\times j!\times S(k,j) i=0∑n(in)j=0∑k(ji)×j!×S(k,j)
改变枚举顺序，就变成了
∑ j = 0 k j ! × S ( k , j ) ∑ i = 0 n ( n i ) ( i j ) \sum_{j=0}^{k}j!\times S(k,j)\sum_{i=0}^{n}{n\choose i}{i\choose j} j=0∑kj!×S(k,j)i=0∑n(in)(ji)
右边那个东西改写一下，得到
∑ j = 0 k j ! × S ( k , j ) ∑ i = 0 n ( n j ) ( n − j i − j ) \sum_{j=0}^{k}j!\times S(k,j)\sum_{i=0}^{n}{n\choose j}{n-j\choose i-j} j=0∑kj!×S(k,j)i=0∑n(jn)(i−jn−j)
如果把 ( n j ) {n\choose j} (jn) 拿出来，惊讶地发现右边就是一个 2 n − j 2^{n-j} 2n−j 罢了！于是
a n s = ∑ j = 0 k j ! × S ( k , j ) × ( n j ) × 2 n − j ans=\sum_{j=0}^{k}j!\times S(k,j)\times{n\choose j}\times 2^{n-j} ans=j=0∑kj!×S(k,j)×(jn)×2n−j
话说 j ! × S ( k , j ) j!\times S(k,j) j!×S(k,j) 也可以直接重新定义，即 k k k 个球、 j j j 个不同的盒子，不能空盒。
我们的枚举复杂度是 O ( k ) \mathcal O(k) O(k) 的，不可思议！不过算 S S S 是 O ( k 2 ) \mathcal O(k^2) O(k2) 的递推。
