【题解】 Crash的文明世界

· · 个人记录

P4827 [国家集训队] Crash 的文明世界

教练强推，但我菇了好久

经过递归学习 第二类斯特林数 ，我们可以得到 $$ m^n = \sum\limits_{i=0}^nC_m^i\,* \,i\,! \, * \,S(n,i)$$ $S(i,j)$ 表示把 $n$ 个有标号的球，放入 $j$ 个无标号的盒子，**并且没有空盒子**的方案数。而 $m^n$ 可以表示把 $n$ 个有标号的球，放入 $m$ 个有标号的盒子，**并且允许有空盒子**的方案数。考虑 $C_m^i \,* \, i!$ 的含义，是从 $m$ 个盒子取出 $i$ 个盒子，并且用全排列标号，也就是使无标号的盒子变为有标号的盒子。 只介绍一下 $S(i,j)$，公式是 $S(i,j) = S(\,i-1\,,\,j-1\,) + j \, * \,S(\,i-1\,,\,j\,) $，可以考虑从含义下手去理解这个式子。要么放入一个空盒子，这个方案数是 $S(\,i-1\,,\,j-1\,)$，要么选择放入非空的盒子，这个方案数是 $j\,* \,S(\,i-1\,,\,j-1\,)$。