关于第二类斯特林数的一丢丢东西
第二类斯特林数
S(n,m)表示有(n)个有区别小球，要放进(m)个相同盒子里，且每个盒子非空的方案数
考虑一个很容易的递推：
[S(n,m)=S(n-1,m-1)+m*S(n-1,m)
]
考虑组合意义：
假设前面的(n-1)个球丢进了(m-1)个组，因为每个组非空，所以这个球只有一种选择——自己一组
如果前面的球已经分成了(m)组，那么，这个球就有(m)种放法
所以这个递推式就是这样来的
那么，只考虑组合意义可不可以算？
当然是可以的啦
写式子：
[S(n,m)=frac{1}{m!}sum_{k=0}^{m}(-1)^kC(m,k)(m-k)^n
]
为啥呢？
假设盒子有区别，并且我们允许空盒的存在
显然的，(m^n)就是答案
但是我们当然就是不允许空盒存在啊
所以容斥一下
枚举我当前有几个空盒子存在
那么先把这几个盒子选出来，也就是(C(m,k))
然后剩下(m-k)个盒子，(n)个球可以随便放，也就是((m-k)^n)
最后退出来，我们盒子是没有区别的，所以除以一个(m!)
这样就是直接考虑了
那么，我们来想想一个东西怎么算？
(m^n)怎么算？
考虑一下组合意义，把(n)个有区别的小球分给有区别的(m)个盒子里，允许空盒的方案数
挺好呀，第二类斯特林数是啥意思？
(S(n,m))表示(n)个球丢进(m)个相同盒子里，不允许空盒
好吧，那我枚举一下有(i)个盒子不是空的
再把球丢进盒子不就是(S(n,i)*i!)
所以不就推出来啦？
[m^n=sum_{i=0}^{m}S(n,i)*i!*C(m,i)
]
回来回来，，
如果要算第二类斯特林数，除了(n^2)的递推有没有别的方法呢？
显然是有的
重新看看上面用容斥和组合意义得到的式子
[S(n,m)=frac{1}{m!}sum_{k=0}^{m}(-1)^kC(m,k)(m-k)^n
]
整理一下
[S(n,m)=frac{1}{m!}sum_{k=0}^{m}(-1)^kfrac{m!}{k!(m-k)!}(m-k)^n
]
[S(n,m)=frac{1}{m!}sum_{k=0}^{m}m!frac{(-1)^k}{k!}frac{(m-k)^n}{(m-k)!}
]
[S(n,m)=sum_{k=0}^{m}frac{(-1)^k}{k!}frac{(m-k)^n}{(m-k)!}
]
这样的话，是不是想到了多项式的卷积啦？
于是乎，可以用多项式卷积求出(S(n,X))
复杂度(O(nlogn))