第一类斯特林数

定义:

表示 $n$ 个不同元素形成 $m$ 个圆排列的方案数,记为 $\begin{bmatrix} n \\ m \end{bmatrix}$。

性质:

首先考虑这个怎么求,可以枚举第 $n$ 个元素,它可以自己形成一个新的环,方案数为 $\begin{bmatrix} n-1 \\ m-1 \end{bmatrix}$;它也可以放在已有的 $n-1$ 个元素中一个的后面,方案数为 $(n-1)\begin{bmatrix} n-1 \\ m \end{bmatrix}$,从而得出递推式:

$$\begin{bmatrix} n \\ m \end{bmatrix} = \begin{bmatrix} n-1 \\ m-1 \end{bmatrix} + (n-1)\begin{bmatrix} n-1 \\ m \end{bmatrix}$$

我们设 $f_n(x)$ 为 $\begin{bmatrix} n \\ x \end{bmatrix}$ 的生成函数。根据上面式子可以写出它的生成函数

$$f_n(x)=\prod_{i=0}^{n-1} (x+i)$$

而这个可以直接套用分治 FFT 在 $O ( n \log^2 n )$ 内求出,但我们还可以在它的基础上优化。考虑你目前分治到区间 $(l,r)$,在这之前已经计算出了区间 $(l, mid)$ 的卷积,这个时候应该要递归的计算 $(mid+1, r)$ 的卷积,但其实发现如果你设 $(l, mid)$ 的卷积为 $g(x)$,那么 $(mid+1,r)$ 的卷积就是 $g(x+mid)$。将式子如下化简:

$$\begin{aligned} g(x+mid)=&\sum_{i=0}^{n} a_i(x+mid)^i\\ =&\sum_{i=0}^{n} a_i\sum_{j=0}^i {i\choose j}mid^{i-j}x^j\\ =&\sum_{i=0}^{n} x^i \sum_{j=i}^{n}{i\choose j}mid^{j-i}a_j\\ =&\sum_{i=0}^{n} \frac{x^i}{i!} \sum_{j=i}^{n}\frac{mid^{j-i}}{(j-i)!}a_j*j! \end{aligned}$$

你发现后面的那一块有点像卷积的形式,将其中一项反转后就可以卷起来了,这样我们做到 $O(n \log n)$ 的复杂度

第二类斯特林数

定义:

表示 $n$ 个不同元素拆分为 $m$ 个集合的方案数,记为 $\begin{Bmatrix} n \\ m \end{Bmatrix}$。

性质:

还是先从递推式考虑,枚举第 $n$ 个元素,它可以自己形成一个新的集合,方案数为 $\begin{Bmatrix} n-1 \\ m-1 \end{Bmatrix}$;它也放在已有的 $m$ 个集合中的一个里面,方案数为 $m\begin{Bmatrix} n-1 \\ m \end{Bmatrix} $,从而有递推式:

$$\begin{Bmatrix} n \\ m \end{Bmatrix} = \begin{Bmatrix} n-1 \\ m-1 \end{Bmatrix} + m\begin{Bmatrix} n-1 \\ m \end{Bmatrix}$$

但这个递推式并没有什么用。我们还可以从容斥的角度入手,考虑 $n$ 个元素放在 $m$ 个不同盒子中的方案数就是 $m^n$,而我们把存在空盒子的情况容斥掉后,就是 $m!\begin{Bmatrix} n \\ m \end{Bmatrix}$(因为每个集合是没有区别的),得到式子:
$$\begin{Bmatrix} n \\ m \end{Bmatrix}= \frac{1}{m!} \sum_{i=1}^{m} (-1)^i {m \choose i} (m-i)^n$$

而这个式子稍微有些用,可以化简为:
$$\begin{Bmatrix} n \\ m \end{Bmatrix}= \sum_{i=1}^{m}\frac{(-1)^i}{i!} \frac{(m-i)^n}{(m-i)!}$$

将这个简单卷积后也能在 $O(n \log n)$ 内求出出第二类斯特林数。

斯特林反演

证明不会,形式上类似于二项式反演。。。

$$f(n)=\sum_{k=0}^n \begin{Bmatrix} n \\ m \end{Bmatrix} g(k)$$
$$ g(n)=\sum_{k=0}^n (-1)^{n-k} \begin{bmatrix} n \\ m \end{bmatrix} f(k)$$

斯特林数与阶乘幂

斯特林子集数是产生通常幂的阶乘幂的系数

$$x^n= \sum_{i=0} ^n \begin{Bmatrix} n \\ i \end{Bmatrix} x^{\underline i}$$

$$x^\overline n=\sum_{i=0}^n \begin{bmatrix} n \\ m \end{bmatrix} x^i$$

根据第一个式子我们可以解决自然数幂和这个问题:

$$\begin{aligned} \sum_{i=1}^{n} i^k =&\sum_{i=1} ^n \sum_{j=0}^k \begin{Bmatrix} k \\ j \end{Bmatrix} x^{\underline j} \\ =& \sum_{i=1} ^n \sum_{j=0}^k \begin{Bmatrix} k \\ j \end{Bmatrix} j! {i\choose j} \\=& \sum_{j=0}^k \begin{Bmatrix} k \\ j \end{Bmatrix} j!\sum_{i=j}^n{i\choose j} \\=&\sum_{j=0}^k \begin{Bmatrix} k \\ j \end{Bmatrix} j! {i\choose j}\\=&\sum_{j=0}^k \begin{Bmatrix} k \\ j \end{Bmatrix} \frac{(n+1)^\underline {j+1}}{j+1} \end{aligned} $$

这样一来,利用一开始提到求解斯特林数的方法,就可以在 $O(k \log k)$ 内解决自然数幂和。除此之外利用拉格朗日插值还可以在 $O(k)$ 内解决这个问题,这里就不多说了。

例题

1.CF960G Bandit Blues

代码链接

发表评论

邮箱地址不会被公开。 必填项已用*标注