POJ 1430 Binary-Stirling-Numbers

zcmimi at 
查看原题'" class='mdui-btn mdui-btn-raised'>点击加载点击跳转第二类斯特林数将$n$个不同的球放进$m$个相同的盒子,保证盒子非空,求方案数。容斥法:$S(n,m)=\frac 1{m!}\sum_{i=0}^m {m\choose i}(m-i)^n(-1)^i$枚举空盒个数,剩下随便放,到这里开始也有了二项式反演的形式由于盒子相同,所以除以$m!$递推法:$S(n,m)=S(n-1,m-1)+mS(n-1,m)$相当于考虑现在要放的求是否单独在一个盒子里:不占一盒:其余$n-1$个球放到$m-1$个盒子里放到某个有球的盒子里:有$m$个盒子可放($m$种可……