rt,

$dp_{i,j}=(i-1)\times dp_{i-1,j}+dp_{i-1,j-1}$。

（尽量优化到不高于 $\mathcal{O(n \log n)}$）。