在线欧美人妻,久久精品中文字幕女同

請(qǐng)大家注意：

因?yàn)樽髡邔?xiě)的文章中的梯等式公式總是莫名的顯示錯(cuò)誤，所以作者的許多文章中的梯等式都暴力拆成一步一個(gè)等式了。
造成的不適，請(qǐng)諒解。
同時(shí)，如果文章中還有其他錯(cuò)誤，請(qǐng)聯(lián)系作者，謝謝。

問(wèn)題模型

求將 $n$ 個(gè)數(shù)劃分成 $m$ 個(gè)圓排列的方案數(shù)。
求將 $n$ 個(gè)數(shù)劃分成 $m$ 個(gè)集合的方案數(shù)，集合沒(méi)有標(biāo)號(hào)。

公式推導(dǎo)——遞推

我們
設(shè)第一個(gè)問(wèn)題的答案是 $S_1(n,m)$ ，
設(shè)第二個(gè)問(wèn)題的答案是 $S_2(n,m)$ 。
那么不難寫(xiě)出遞推式：
$S_1(n,m) = S_1(n-1,m-1) + S_1(n-1,m) \times (n-1)$
$S_2(n,m) = S_2(n-1,m-1) + S_2(n-1,m) \times m$

公式推導(dǎo)——拓展

求第一類(lèi)斯特林?jǐn)?shù)的某一行

我們考慮按照遞推式推導(dǎo)出它的生成函數(shù)。
顯然 $S_{1,1}(x) = x$ 。
之后，我們有：
$\begin{align} S_{1,n}(x) &= xS_{1,n-1}(x) + (n-1)S_{1,n-1}(x) \\ &= (x + n-1)S_{1,n-1}(x) \end{align}$
那么不難得出： $S_{1,n}(x) = \prod_{i=0}^{n-1} (x+i)$ ,
我們也可以寫(xiě)成 $S_{1,n}(x) = x^{\overline{n}}$ ,
上面的式子是可以分治 $FFT$ 的，那么我們就可以 $O(n\log^2{n})$ 求出一行了。
在這里我們介紹一種更優(yōu)秀的 $O(n\log{n})$ 的求一行第一類(lèi)斯特林?jǐn)?shù)的方法。
我們考慮倍增求出這個(gè)函數(shù)。
假設(shè)我們已經(jīng)有了 $S_{1,n}(x) = \prod_{i=0}^{n-1} (x+i)$ ，
考慮求出 $S_{1,2n}(x) = \prod_{i=0}^{2n-1} (x+i)$ 。
我們發(fā)現(xiàn) $S_{1,2n}(x) = S_{1,n}(x)S_{1,n}(x+n)$ 。
如果我們可以快速求出 $S_{1,n}(x+n)$ ，就贏了。
顯然 $S_{1,n}(x)$ 是一個(gè)關(guān)于 $x$ 的 $n$ 次多項(xiàng)式，
那么我們?cè)O(shè) $S_{1,n} = \sum_{i=0}^{n} a_i x^i$ ，而 $\{a_i\}$ 是我們已經(jīng)求出來(lái)的。
則
$\begin{align} S_{1,n}(x+n) &= \sum_{i=0}^{n} a_i (x+n)^i \\ &= \sum_{i=0}^{n} a_i \sum_{j=0}^{i} C(i,j) n^{i-j} x^j \\ &= \sum_{j=0}^{n} x^j \sum_{i=j}^{n} C(i,j) n^{i-j} a_i \\ &= \sum_{i=0}^{n} x^i \sum_{j=i}^{n} C(j,i) n^{j-i} a_j \\ &= \sum_{i=0}^{n} x^i \sum_{j=i}^{n} \frac{j!}{i!(j-i)!} n^{j-i} a_j \\ &= \sum_{i=0}^{n} \frac{x^i}{i!} \sum_{j=i}^{n} \frac{n^{j-i}}{(j-i)!} j! a_j \\ \end{align}$
注意到 $(75)$ 式中，第二個(gè) $\Sigma$ 是一個(gè)減法卷積，那么我們就可以 $NTT$ 了。
于是，我們就可以倍增出 $S_{1,2n}$ 了。
時(shí)間復(fù)雜度 $T(n) = T(\frac{n}{2}) + O(n\log{n}) = O(n\log{n})$ 。

第一類(lèi)斯特林?jǐn)?shù)和階乘

由第一類(lèi)斯特林?jǐn)?shù)的定義，顯然 $n! = \sum_{i=0}^{n} S_1(n,i)$ 。
這是由排列與置換和輪換的關(guān)系推導(dǎo)出來(lái)的。

第一類(lèi)斯特林?jǐn)?shù)和上升/下降冪

因?yàn)榈谝活?lèi)斯特林?jǐn)?shù)的生成函數(shù)就是 $x^{\overline{n}}$ ，
所以接下來(lái)我們考慮下降冪的展開(kāi)：
$x^{\underline{n}} = (-x)^{\overline{n}} \times (-1)^n$
$x^{\underline{n}} = (-1)^n\sum_{i=0}^{n} S_1(n,i) (-x)^i$
$x^{\underline{n}} = (-1)^n\sum_{i=0}^{n} S_1(n,i) (-1)^i x^i$
$x^{\underline{n}} = \sum_{i=0}^{n} S_1(n,i) (-1)^{n-i} x^i$
于是我們就可以定義出有符號(hào)第一類(lèi)斯特林?jǐn)?shù)。
及 $S_1'(n,m) = (-1)^{n-m}S_1(n,m)$ 。
并且有符號(hào)第一類(lèi)斯特林?jǐn)?shù)的生成函數(shù)就是 $\prod_{i=0}^{n-1}(x-i) = x^{\underline{n}}$ 。

第二類(lèi)斯特林?jǐn)?shù)和自然數(shù)的冪

我們考慮 $n^k$ 的組合意義：有 $n$ 個(gè)有標(biāo)號(hào)的盒子，有 $k$ 個(gè)有標(biāo)號(hào)的球，每個(gè)球隨便放的方案數(shù)。
因?yàn)槲覀冇?img class="math-inline" src="https://math.jianshu.com/math?formula=S_2(k%2Cm)" alt="S_2(k,m)" mathimg="1">表示將 $k$ 個(gè)有標(biāo)號(hào)的球分成 $m$ 個(gè)非空集合的方案數(shù)。
那么我們不難寫(xiě)出：
$n^k = \sum_{i=0}^{k} C(n,i) S_2(k,i) i!$
$n^k = \sum_{i=0}^{k} S_2(k,i) n^{\underline{i}}$
其實(shí)就是枚舉在 $n$ 個(gè)盒子中用了幾個(gè)，盒子還有標(biāo)號(hào)，所以乘階乘。

求第二類(lèi)斯特林?jǐn)?shù)的某一行

我第一眼看到 $(81)$ 式，覺(jué)得好像可以二項(xiàng)式反演？
那么我們?cè)O(shè)：
$f_k(n) = n^k$
$g_k(n) = S_2(k,n) n!$
于是， $(81)$ 式就可以寫(xiě)成：
$f_k(n) = \sum_{i=0}^{k} C(n,i) g_k(i)$
$f_k(n) = \sum_{i=0}^{n} C(n,i) g_k(i)$
這顯然可以二項(xiàng)式反演：
$g_k(n) = \sum_{i=0}^{n} C(n,i) (-1)^{n-i} f_k(i)$
那么我們其實(shí)就已經(jīng)推出 $S_2(k,n)$ 的通項(xiàng)公式了：
$n!\ S_2(k,n) = \sum_{i=0}^{n} C(n,i) (-1)^{n-i} i^k$
$\begin{align} S_2(n,m) &= \frac{1}{m!} \sum_{i=0}^{m} C(m,i) (-1)^{m-i} i^n \\ &= \frac{1}{m!} \sum_{i=0}^{m} C(m,i) (-1)^i (m-i)^n \\ &= \sum_{i=0}^{m} \frac{(-1)^i}{i!} \times \frac{(m-i)^n} {(m-i)!} \end{align}$
這樣，我們就可以 $O(n\log{n})$ 求出第二類(lèi)斯特林?jǐn)?shù)的一行了。

兩類(lèi)斯特林?jǐn)?shù)的生成函數(shù)

為了表示清晰，我們用

$S_{1,n}(x)$ 表示第一類(lèi)斯特林?jǐn)?shù)第 $n$ 行的生成函數(shù)。
$S_{2,n}(x)$ 表示第二類(lèi)斯特林?jǐn)?shù)第 $n$ 行的生成函數(shù)。
$T_{1,n}(x)$ 表示第一類(lèi)斯特林?jǐn)?shù)第 $n$ 列的生成函數(shù)。
$T_{2,n}(x)$ 表示第二類(lèi)斯特林?jǐn)?shù)第 $n$ 列的生成函數(shù)。

那么通過(guò)遞推式，我們可以得出：

第一類(lèi)斯特林?jǐn)?shù)——行：
$S_{1,n}(x)= \begin{cases} 1, & n=0 \\ (x+n-1)S_{1,n-1}(x), & n \geq 1 \end{cases}$

第二類(lèi)斯特林?jǐn)?shù)——行：
$S_{2,n}(x)= \begin{cases} 1, & n=0 \\ x(S'_{1,n-1}(x)+S_{1,n-1}(x)), & n \geq 1 \end{cases}$

第二類(lèi)斯特林?jǐn)?shù)——列：
$S_2(n,m) = S_2(n-1,m-1) + mS_1(n-1,m)$
$T_2(m,n) = T_2(m-1,n-1) + mT_1(m,n-1)$
$T_{2,m}(x) = xT_{2,m-1}(x) + mxT_{2,m}$
$(1-mx)T_{2,m}(x) = xT_{2,m-1}(x)$
$T_{2,m}(x) = \frac {x T_{2,m-1} (x)} {1-mx}$
$T_{2,m}(x) = \frac{x}{1-mx}T_{2,m-1}(x)$
$T_{2,m}(x) = \frac{x^m}{\prod_{i=1}^{m}(1-ix)}$
此時(shí)我們可以在用之前的倍增做法將 $O(n\log^2{n})$ 優(yōu)化至 $O(n\log{n})$ 。

第一類(lèi)斯特林?jǐn)?shù)——列：放棄?。?！看 $Luogu$ 題解吧。。。

斯特林反演——反轉(zhuǎn)公式

給出一個(gè)顯然~~而且之前也用過(guò)~~的式子：
$x^{\overline{n}} = (-1)^n (-x)^{\underline{n}}$
$x^{\underline{n}} = (-1)^n (-x)^{\overline{n}}$
那么我們將其代入之前的一個(gè)式子：
$\begin{align} n^m &= \sum_{k=0}^{m} S_2(m,k) n^{\underline{k}} \\ &= \sum_{k=0}^{m} S_2(m,k) (-1)^k (-n)^{\overline{k}} \end{align}$
此時(shí)我們想到第一類(lèi)斯特林?jǐn)?shù)的生成函數(shù)，有：
$n^m = \sum_{k=0}^{m} S_2(m,k) (-1)^k (-n)^{\overline{k}}$
$n^m = \sum_{k=0}^{m} S_2(m,k) (-1)^k \sum_{j=0}^{k} S_1(k,j) (-n)^j$
$n^m = \sum_{j=0}^{m} n^j \sum_{k=j}^{m} S_2(m,k) S_1(k,j) (-1)^{k-j}$
對(duì)比兩側(cè)的系數(shù)，而且這個(gè)式子對(duì)于任意 $n$ 都滿(mǎn)足，所以有：
$\sum_{k=j}^{m} S_2(m,k) S_1(k,j) (-1)^{k-j} = [j=m]$
如果我們是用 $n^{\underline{m}}$ 來(lái)推導(dǎo)還可以得到另一個(gè)式子：
$\sum_{k=j}^{m} S_1(m,k) S_2(k,j) (-1)^{k-j} = [j=m]$
放在一起就是：
$\begin{align} \sum_{k=j}^{m} S_2(m,k) S_1(k,j) (-1)^{k-j} &= [j=m] \\ \sum_{k=j}^{m} S_1(m,k) S_2(k,j) (-1)^{k-j} &= [j=m] \end{align}$

斯特林反演——反演公式：

假設(shè)我們知道 $f(n) = \sum_{i=0}^{n} S_2(n,i) g(i)$ ，
求 $g(n)$ 關(guān)于 $f(i)$ 的表達(dá)式。
我們考慮一個(gè)及其顯然的式子：
$g(n) = \sum_{i=0}^{n} [i=n] g(i)$
$g(n) = \sum_{i=0}^{n} \left(\sum_{j=i}^{n} S_1(n,j)S_2(j,i)(-1)^{n-j}\right)g(i)$
$g(n) = \sum_{i=0}^{n} \left(\sum_{j=0}^{n} S_1(n,j)S_2(j,i)(-1)^{n-j}\right)g(i)$
$g(n) = \sum_{j=0}^{n} (-1)^{n-j} S_1(n,j) \sum_{i=0}^{n} S_2(j,i) g(i)$
$g(n) = \sum_{j=0}^{n} (-1)^{n-j} S_1(n,j) f(j)$
$g(n) = \sum_{i=0}^{n} (-1)^{n-i} S_1(n,i) f(i)$
同理，那么我們可以得到這些公式：
$f(n) = \sum_{i=0}^{n} S_2(n,i) g(i) \Leftrightarrow g(n) = \sum_{i=0}^{n} (-1)^{n-i} S_1(n,i) f(i)$
$f(n) = \sum_{i=0}^{n} S_1(n,i) g(i) \Leftrightarrow g(n) = \sum_{i=0}^{n} (-1)^{n-i} S_2(n,i) f(i)$