第二类斯特林数小结

定义

第二类斯特林数$S(n,m)$表示的是把$n$个不同的小球放在$m$个相同的盒子里方案数。

求法

递推

递推的求法很常见啦,这里就只写式子了:
$$S(n,m)=S(n-1,m-1)+S(n-1,m) \times m$$
边界是$S(0,0)=1$

容斥

先上式子:
$$S(n,m)=\frac{1}{m!}\sum_{k=0}^{m}(-1)^kC(m,k)(m-k)^n$$
解释一下,这里的容斥利用的是,枚举有几个集合是空的,然后注意到每个集合都是一样的,所以最后要除一个$m!$。注意到这个式子是一个卷积的形式,所以我们可以利用NTT在$O(n\log n)$的复杂度内,预处理出所有的$S(n,i),1\leqslant i \leqslant n$。为什么这个式子可以NTT呢?好像不太明显,我们把组合数拆开,原式化为:
$$S(n,m)=\frac{1}{m!}\sum_{k=0}^{m}(-1)^k\frac{m!}{k!(m-k)!}(m-k)^n$$
整理一下,就可以变成:
$$S(n,m)=\sum_{k=0}^{m}[\frac{(-1)^k}{k!}] \times [\frac{(m-k)^n}{(m-k)!}]$$
这下子,卷积的形式就很明显了,于是我们也就可以用NTT实现了。

一些性质

一个常用的转化

$$n^k=\sum_{i=0}^{k}S(k,i) \times C(n,i) \times i!$$
证明可以考虑组合意义,等式的左边就是把$k$个球放到$n$个盒子里;右边就是枚举非空盒子的数量$i$。注意到这里的盒子是不同的,所以还要乘上一个$i!$。

斯特林反演

设$S_1$表示第一类斯特林数,$S_2$表示第二类斯特林数。
若函数$f(x)$满足

$$f(n)=\sum_{i=1}^{n}S_2(n,i)g(i)$$

则有

$$g(n)=\sum_{i=1}^{n}(-1)^{n-i}S_1(n,i)f(i)$$

例题

BZOJ2159 Crash的文明世界

题意

Crash小朋友最近迷上了一款游戏——文明5(Civilization V)。在这个游戏中,玩家可以建立和发展自己的国家,通过外交和别的国家交流,或是通过战争征服别的国家。现在Crash已经拥有了一个$n$个城市的国家,这些城市之间通过道路相连。由于建设道路是有花费的,因此Crash只修建了$n-1$条道路连接这些城市,不过可以保证任意两个城市都有路径相通。在游戏中,Crash需要选择一个城市作为他的国家的首都,选择首都需要考虑很多指标,有一个指标是这样的:$$S(i)=\sum_{i=1}^{n}dist(i,j)^k$$其中$S(i)$表示第$i$个城市的指标值,$dist(i,j)$表示第$i$个城市到第$j$个城市需要经过的道路条数的最小值,$k$为一个常数且为正整数。因此Crash交给你一个简单的任务:给出城市之间的道路,对于每个城市,输出这个城市的指标值,由于指标值可能会很大,所以你只需要输出这个数$\mod 10007$的值。
$n \leqslant 50000,k \leqslant 150$。

题解

利用上面写的那个常用的转化。令$dp[i][j]=\sum\limits_{k=1}^{n}C(dist(i,k),j)$,那么答案$ans_i$就可以表示为$ans_i=\sum\limits_{j=1}^{k}S(k,j) \times j! \times dp[i][j]$。注意到$dp[i][j]$是组合数,是可以直接转移的,所以直接转就可以了。于是时间复杂度就是$O(nk+k^2)$。