特殊的数
特殊的数
本文参考了《具体数学——计算机科学基础》的第六章内容，如有侵犯版权，请联系我，我会马上做出声明或修改。
另外，阅读本文，你可能需要先阅读及
在信息学的学习中，我们通常会遇到很多特殊的数，科学家们赋予了它们特殊的名字，我们可以通过它们特殊的性质解决很多棘手的问题。
1. 斯特林数 Stirling numbers
斯特林数又有第一类斯特林数和第二类斯特林数，一般我们从第二类开始讲起，因为第二类斯特林数要比第一类更为常用，也更适合入门。
1.1. 斯特林数的认识
我们定义第二类斯特林数 \(\begin{Bmatrix}n\\k\end{Bmatrix}\) 表示将 \(n\) 个元素划分成 \(k\) 个集合的方案数，也可以记为 \(S(n,k)\)。
那么，我们很容易求出一些边界，\(S(0,0)=1,S(1,0)=S(2,0)=\dots=0,S(i,i)=1\) 等。
我们考虑求出 \(\begin{Bmatrix}n\\k\end{Bmatrix}\) 的递推公式。
我们考虑第 \(n\) 个元素如何分组。它可以自己分成一个新组，也可以加入其他任意一组，所以：
\[\begin{Bmatrix}n\\k\end{Bmatrix}=k\begin{Bmatrix}n-1\\k\end{Bmatrix}+\begin{Bmatrix}n-1\\k-1\end{Bmatrix},(n>0) \]我们便得到了第二类斯特林数的递推公式。
我们类似地定义第一类斯特林数 \(\begin{bmatrix}n\\k\end{bmatrix}\) 表示将 \(n\) 个元素划分成 \(k\) 个环的方案数，也可以记为 \(s(n,k)\)。
根据定义及前面所学，我们知道，对于一个 \(k\) 个元素的集合，能划分成 \((k-1)!\) 个不同的环，所以，我们有以下不等式成立：
\[\begin{Bmatrix}n\\k\end{Bmatrix}\le\begin{bmatrix}n\\k\end{bmatrix},(0\le k\le n) \]对于 \(k>0\) 的情况，\((k-1)!\ge1\)，上述不等式成立，对于 \(k=0\) 的情况，会发现 \(\begin{bmatrix}0\\0\end{bmatrix}=1,\begin{bmatrix}i\\0\end{bmatrix}=0\)，满足 \(\begin{bmatrix}n\\0\end{bmatrix}=\begin{Bmatrix}n\\0\end{Bmatrix}\)，不等式取等号。
我们类似地考虑如何递推出 \(\begin{bmatrix}n\\k\end{bmatrix}\)，同样考虑第 \(n\) 个元素分到哪里。它可以独自分成一个新的环，也可以加入到之前任意一个位置。
具体有多少个位置呢，我们可以考虑顺时针下每个元素的左侧都计算一次，这样就能不重不漏的算出，总共有 \(n-1\) 个空位可以放。
所以：
\[\begin{bmatrix}n\\k\end{bmatrix}=(n-1)\begin{bmatrix}n-1\\k\end{bmatrix}+\begin{bmatrix}n-1\\k-1\end{bmatrix} \]至此，我们对两类斯特林数有了大致的认识，接下来我们就要发觉它们的性质了。
1.2. 斯特林数的性质
斯特林数具有许多优美的性质
性质 1.2.0：\(\sum\limits_{k=0}^n\begin{bmatrix}n\\k\end{bmatrix}=n!\),(\(n\ge0\) 且 \(n\) 是整数)
这个性质暴力拆开用归纳法应该也是能证明的，但是这个做法并不优美，我们考虑从组合意义的角度入手。
上述性质等号左边可以看做 \(n\) 个元素划分出任意个环的方案数，右边可以看做一个长度为 \(n\) 的排列。
如果我们证明出两者双射，那么也就证明出了性质 1.2.0。
对于一个长度为 \(n\) 的排列 \(\pi_1,\pi_2,\dots,\pi_m\)，我们构造一个 \(n\) 个点，\(n\) 条边的图，对于每一个 \(1\le i\le n\)，让点 \(i\) 向 \(\pi_i\) 连边，这样，最后就会形成若干个环，对应一种划分环的方案。
而对于一个划分环的方案，我们对每一个环钦定一个方向，对于每个元素 \(i\)，让 \(\pi_i\) 为它顺时针往下的方案数，最终也会形成一个排列。
至此，我们证明出了 \(n\) 个元素划分出任意个环的方案数和一个长度为 \(n\) 的排列两者双射，性质成立。
性质 1.2.1：\(x^n=\sum\limits_{k=0}^n\begin{Bmatrix}n\\k\end{Bmatrix}x^{\underline k}\),(\(n\ge0\) 且 \(n\) 是整数)。
这里我们最好需要一个更严谨的定义：
对于 \(n\ge0\) 且 \(k<0\)，我们定义 \(\begin{Bmatrix}n\\k\end{Bmatrix}=\begin{bmatrix}n\\k\end{bmatrix}=0\)。
还有就是上面的下降次幂多项式还没有定义，需要补充一下：
我们定义一个 \(m\) 次下降次幂多项式 \(x^{\underline m}=x\times(x-1)\times(x-2)\times\dots\times(x-m+1)\)。
有了这个定义，性质 1.2.1 就可以用归纳法简单证明。
但是在证明这个性质之前，我们先证明另一个性质热热身：
性质 1.2.1.1：\(x\cdot x^{\underline k}=x^{\underline {k+1}}+k\cdot x^{\underline k}\),(\(k\ge0\) 且 \(k\) 是整数)。
用归纳法非常好证，因为 \(x^{\underline{k+1}}=(x-k)x^{\underline k}=x\cdot x^{\underline k}-k\cdot x^{\underline k}\)，移一下项即可得证。
回到性质 1.2.1，首先有 \(x^0=x^{\underline 0},x^1=x^{\underline 1},x^2=x^{\underline 2}+x^{\underline 1}\) 等显然成立。
我们假设 \(x^{n-1}=\sum\limits_{k=0}^{n-1}\begin{Bmatrix}n-1\\k\end{Bmatrix}x^{\underline k}\)，那么：
\[x^n=x\cdot x^{n-1} \]\[x^n=\sum\limits_{k=0}^{n-1}\begin{Bmatrix}n-1\\k\end{Bmatrix}x\cdot x^{\underline k} \]这时候用我们热身时候的性质 1.2.1.1：
\[x^n=\sum_{k=0}^{n-1}\begin{Bmatrix}n-1\\k\end{Bmatrix}(x^{\underline {k+1}}+k\cdot x^{\underline k}) \]然后拆开括号：
\[x^n=\sum_{k=0}^{n-1}\begin{Bmatrix}n-1\\k\end{Bmatrix}x^{\underline {k+1}}+\sum_{k=0}^{n-1}\begin{Bmatrix}n-1\\k\end{Bmatrix}k\cdot x^{\underline k} \]左边的 \(k+1\) 有点丑，我们用 \(k\) 替换 \(k+1\)
\[x^n=\sum_{k=1}^{n}\begin{Bmatrix}n-1\\k-1\end{Bmatrix}x^{\underline k}+\sum_{k=0}^{n-1}\begin{Bmatrix}n-1\\k\end{Bmatrix}k\cdot x^{\underline k} \]根据刚才更加严谨的定义，我们可以调整一下求和的上下界，并把它们合并：
\[x^n=\sum_{k=0}^{n}(\begin{Bmatrix}n-1\\k-1\end{Bmatrix}+k\begin{Bmatrix}n-1\\k\end{Bmatrix})\cdot x^{\underline k} \]发现中间那个就是第二类斯特林数的递推公式，所以：
\[x^n=\sum_{k=0}^n\begin{Bmatrix}n\\k\end{Bmatrix}x^{\underline k} \]性质成立。
性质 1.2.2：\(x^{\overline n}=\sum\limits_{k=0}^n\begin{bmatrix}n\\k\end{bmatrix}x^k\),(\(n\ge0\) 且 \(n\) 是整数)。
我们类似地定义上升次幂多项式：
我们定义一个 \(m\) 次上升次幂多项式 \(x^{\overline m}=x\times(x+1)\times(x+2)\times\dots\times(x+m-1)\)。
具体证明同样可以类似的用归纳法来证，这里留给读者思考吧。其实就是我懒。
性质 1.2.1 教会了我们如何用下降次幂多项式表示成通常幂，性质 1.2.2 教会了我们如何用通常幂表示上升次幂多项式，那么如何反过来呢？
发现这个东西和当初我们介绍反演的时候很像。我们是否可以用之前的方法，乘上某一个系数构造出一个类似地恒等式？
性质 1.2.3：若 \(n\ge0\) 且 \(n\) 是整数，则：
\[x^n=\sum\limits_{k=0}^n\begin{Bmatrix}n\\k\end{Bmatrix}(-1)^{n-k}x^{\overline k} \]\[x^{\underline n}=\sum\limits_{k=0}^n\begin{bmatrix}n\\k\end{bmatrix}(-1)^{n-k}x^{k} \]
我们发现上升次幂多项式和下降次幂多项式很像，不过系数的符号不太一样，所以乘上一些 \(-1\) 即可。
也就是说，有 \(x^{\underline n}=(-1)^n(-x)^{\overline n}\) 成立，通过这个可以得证。
因此，我们可以利用这几个性质完成几个幂次之间的转化。
性质 1.2.4（反转公式）：若 \(0\le m\le n\) 且 \(n,m\) 均是整数，则：
\[\sum\limits_k\begin{bmatrix}n\\k\end{bmatrix}\begin{Bmatrix}k\\m\end{Bmatrix}(-1)^{n-k}=[n=m] \]\[\sum\limits_k\begin{Bmatrix}n\\k\end{Bmatrix}\begin{bmatrix}k\\m\end{bmatrix}(-1)^{n-k}=[n=m] \]
\(n=m\) 的时候显然成立，其他情况分别把性质 1.2.1 带入性质 1.2.3.2，性质 1.2.2 带入性质 1.2.3.1 即可得证。
斯特林数的性质还有很多，还有一些是和二项式系数有很大的关系，但是很多性质比较冷门，而且证明过程比较复杂，这里不再赘叙。
有兴趣可以去看《具体数学》的表 6-4，里面列举了很多很详细的斯特林数恒等式，若有时间，我也会去写这些恒等式的详细证明。
另外，根据反转公式，我们也有了斯特林数反演：
性质 1.2.5：对于两个数论函数 \(f(n),g(n)\)：
\(f(n)=\sum_{k=0}^n\begin{Bmatrix}n\\k\end{Bmatrix}g(k)\Longleftrightarrow g(n)=\sum_{k=0}^n\begin{bmatrix}n\\k\end{bmatrix}(-1)^{n-k}f(k)\)。
上述讨论都是在 \(n,m\) 为非负整数的范围，如果我们把斯特林数的范围扩展到 \(n,k\le0\) 的情况，并让它继续满足斯特林数的递推式，会发生什么呢？如果你有兴趣的话，可以写出 \(n,k\in[-5,5]\) 的斯特林数三角形，你就会惊奇的发现：
性质 1.2.6：若 \(n,k\) 为整数，则：
\[\begin{Bmatrix}n\\k\end{Bmatrix}=\begin{bmatrix}-n\\-k\end{bmatrix} \]
是的，斯特林数同样满足很优美的对称性，对偶性，简直是天生一对！
1.3 斯特林数的求法
了解完斯特林数的相关性质，如何快速求斯特林数呢？
首先，根据斯特林数的递推式，我们能够轻松在 \(O(n^2)\) 的时间内打表求出两类斯特林数。
如果我们需要更快的时间呢？
问题 1.3.1（第二类斯特林数·行）：快速求出一行第二类斯特林数。
我们可以利用性质 1.2.1，暴力把 \(x^{\underline n}\) 给算出来，分治 NTT 做到 \(O(n\log^2n)\) 的时间，倍增可以更优。
但是还有更加优美的做法。
第二类斯特林数还有一个性质：
\[k^n=\sum_{i=0}^k\dbinom ki\begin{Bmatrix}n\\i\end{Bmatrix}i! \]发现这个东西可以二项式反演，按照反演套路，假设 \(f(k)=k^n\)，\(g(k)=\begin{Bmatrix}n\\k\end{Bmatrix}k!\)，
然后就有：
\[f(k)=\sum_{i=0}^k\dbinom kig(i) \]然后我们直接上公式：
\[g(k)=\sum_{i=0}^k\dbinom kif(k)(-1)^{k-i} \]把 \(f(k),g(k)\) 带进去，拆开组合数：
\[\begin{Bmatrix}n\\k\end{Bmatrix}k!=\sum_{i=0}^k\frac{k!}{i!(k-i)!}i^n(-1)^{k-i} \]约掉 \(k!\)：
\[\begin{Bmatrix}n\\k\end{Bmatrix}=\sum_{i=0}^k\frac{i^n(-1)^{k-i}}{i!(k-i)!} \]发现是个卷积形式，直接上 NTT 即可做到 \(O(n\log n)\)。
signed main(){
scanf("%lld",&n);init(n<<2);
f[0]=0,g[0]=1;int ifac=1;
for(int i=1;i<=n;i++){
ifac=ifac*inv[i]%p;
f[i]=ifac*qpow(i,n)%p;
g[i]=g[i-1]*(p-inv[i])%p;
}
Mul(f,g,n,n+1);
print(f,n);
}
评测记录
问题 1.3.2（第一类斯特林数·行）：快速求出一行第一类斯特林数。
用性质 1.2.3.2，与第二类斯特林数·行倍增的做法类似。
我们相当于要求出 \(x^{\overline n}\) 展开后每一项系数，考虑倍增，假设我们已经求出了 \(f^*(x)=x^{\overline m}=\sum\limits_{i=0}^ma_ix^i\)，那么有：
\[f(x)=x^{\overline {2m}}=x^{\overline m}\times (x+n)^{\overline m}=f^*(x)f^*(x+n) \]接下来的问题，相当于就是已知 \(f(x)\)，求 \(f(x+n)\)。
\[f(x+n)=\sum_{i=0}^ma_i(x+n)^i \]组合数展开二项式：
\[f(x+n)=\sum_{i=0}^ma_i\sum_{j=0}^i\dbinom ijx^jn^{i-j} \]调换求和顺序：
\[f(x+n)=\sum_{j=0}^mx^j\sum_{i=j}^{m}a_in^{i-j}\dbinom ij \]暴力拆开组合数：
\[f(x+n)=\sum_{j=0}^m\frac{j!x^j}{n^j}\sum_{i=j}^m(a_in^ii!)\cdot\frac{1}{(i-j)!} \]做一个差卷积即可。
写了个递推做法，降低常数：
void S1(int *f,int n){
static int g[N],h[N];
int top=0,st[30],m=1;
while(n)st[++top]=n&1,n>>=1;
--top,n=f[1]=1;
while(top){
cpy(g,f,n+1);px(g,fac,n+1);
rev(g,n);
for(int i=0;i<=n;i++)h[i]=qpow(n,i)*ifac[i]%p;
while(m<=(n<<1))m<<=1;
Mul(g,h,m>>1,m);clr(h,m);rev(g,n);
px(g,ifac,n+1);clr(g+n+1,m-n);
Mul(f,g,m>>1,m);n<<=1;clr(g,m);
if(st[top--])
for(int i=(n|=1);i>=1;i--)f[i]=(f[i-1]+(n-1)*f[i]%p)%p;
clr(f+n+1,m-n);
}
clr(g,n+1),clr(h,n+1);
}
评测记录
问题 1.3.3（第二类斯特林数·列）：快速求出一列的第二类斯特林数。
提供两种不同的做法：
做法一：EGF+exp。
如果我们考虑把原本无序的 \(k\) 个集合换成有序的 \(k\) 个盒子，那么会使得答案多成上一个 \(k!\)，最后除掉就可以了。
对于每个盒子，如果不加限制的放，那么它的 EGF 就是 \(G(x)=\sum\limits_{i\ge0}\dfrac{x^i}{i!}=e^x\)，但是盒子不能为空，所以要减去 \(1\)，所以 \(G(x)=e^x-1\)。
\(k\) 个盒子的 EGF 就是：\(F(x)=G^k(x)\)，直接暴力 exp 即可。
做法二：倍增 NTT。
我们假设第 \(k\) 列的答案多项式为 \(F_k(x)\)，那么：
\[F_k(x)=\sum_{i\ge0}\begin{Bmatrix}i\\k\end{Bmatrix}x^i \]把递推式按上去：
\[F_k(x)=\sum_{i\ge0}(k\begin{Bmatrix}i-1\\k\end{Bmatrix}+\begin{Bmatrix}i-1\\k-1\end{Bmatrix})x^i \]拆开：
\[F_k(x)=kxF_k(x)+xF_{k-1}(x) \]移项：
\[F_k(x)=\frac{xF_{k-1}(x)}{1-kx} \]边界：\(F_0(x)=1\)，所以我们可以得出：
\[F_k(x)=x^k\prod_{i=1}^k\frac 1{1-ix} \]前面的一切好说，我们只需要能够快速求出 \(\prod\limits_{i=1}^k(1-ix)\) 即可。
我们对这个式子动一些手脚：
\[\prod_{i=1}^k(1-ix)=x^k\prod_{i=1}^k(x^{-1}-i) \]我们在学多项式带余除法时用过一个翻转操作，就是把 \(x\) 代替成 \(x^{-1}\)，\((x^{-1}-i)\) 其实就是 \((x-i)\) 的翻转。
那么，我们现在要求的就是 \(\prod\limits_{i=1}^k(x-i)=\dfrac{x^{\underline{k+1}}}{x}\)，发现是老朋友了，上面的同款倍增方法再来一遍。
两个方法时间复杂度都是 \(O(n\log n)\)，但下面倍增的常数更小。
因为我是口胡大师，所以我还没写，就不贴代码了。
问题 1.3.4（第一类斯特林数·列）：快速求出一列第一类斯特林数。
同样不考虑 \(k\) 个环，假设它们互不相同，最后求出答案再除掉 \(k!\)。
只有一个圆排列的 EGF 显然就是 \(F(x)=\sum\limits_{i\ge0}(i-1)!\dfrac{x^i}{i!}=\ln(1+x)\)，那么 \(k\) 个圆排列的 EGF 就是 \((\ln(1+x))^k\)，\(\ln\) 部分写开来，直接上多项式 pow。
呼，深吸一口气，看到这里，你终于学会了一些斯特林数的基本操作了。