Stirling数是组合数学中两类很重要的数，分为第一类Stirling数和第二类Stirling数。

我先声明一下苏联式记法和美国式记法。对于组合数，苏联式记法是C_m^n，美国式记法是小括号里面上m下n，上下关系恰好与苏联式记法相反。虽然英美与西欧等大多通用美国式记法，但是俄罗斯以及东欧国家流行苏联式记法，并且我国的高中课本与高考也通用组合数的苏联式记法。

那么同样的，虽然Stirling数在西方有着类似的中括号与大括号的记法，我还是综合了国内的一些参考书，给了以下定义：

第一类Stirling数，记作小写字母s，加下角标1。即：

$$s_1(n,k)$$

第二类Stirling数，记作大写字母S，加下角标2。即：

$$S_2(n,k)$$

这样无论是常见的大小写，还是下角标形式记录的Stirling数，全都没有歧义。

一些书上认为第一类Stirling数是全正的，但是绝大多数书上认为第一类Stirling数有正有负。为了方便使用，我们这里的第一类Stirling数是有正有负的。如果对于极少数书上全正的定义，在这里视作第一类Stirling数的绝对值，即|s_1|。

第一类Stirling数s_1(n,k)和置换相关。

置换：1到n的一个排列。例如：6 4 5 2 3 1是长度为6的一个置换。

显然全体长为n的轮换有n!个。全体长为n的置换构成n元对称群。

置换的图：如果第i个位置上的数是j，就从顶点i到j画有向边。

最终置换的图由若干个圈组成，不动点是由顶点指向自身的边构成长为1的圈。

长为k的轮换：对于单位置换1 2 …… n，将其中的k位接连打乱顺序，对应图论中一个长为k的圈。

置换可以看成不相交轮换的乘积。不动点也看作一个轮换。

一个置换恰含k个轮换：恰好可以写成k个不相交轮换的乘积，即图中恰好有k个连通分支。

给出绝对值的定义：|s_1(n,k)|是全体置换中，恰含k个轮换的置换个数。

符号的定义如下：

$$s_1(n,k)={(-1)}^{n-k}|s_1(n,k)|$$

即当n与k的奇偶性相同为正，不同为负。

显然，n!是带绝对值的第n行第一类Stirling数的和。有一个定理是说，如果不带绝对值，有正有负，那么除了第一行第一类Stirling数的和是1以外，其余的行第一类Stirling数的和全是0。

第二类Stirling数与集合的划分有关。

给出定义：S_2(n,k)是把集合1……n分成k个非空子集的划分个数。

Bell数与第二类Stirling数相关。第n个Bell数记作B_n。

Bell数和Bernoli数没什么关系，极少同时出现。我的习惯是将Bell数记作大写，将Bernoli数记作小写，或者提前声明是哪一种数。

本文中的B_n全部都是Bell数，与Bernoli数无关。

给出定义：B_n是把集合1……n分成非空子集的划分个数。

因此B_n是第n行第二类Stirling数的和。

自0开始的Bell数：

研究组合数学，必须要有数表。

第一类Stirling数的数表如下：

第二类Stirling数的数表如下：

一些数感较好的人往往可以从数表中找到许多灵感。我们可以看到，第一类Stirling数的绝对值，增长速度比第二类Stirling数要快。

首先限定下面几个式子的n的全体，n_1到n_k为正整数，并且：

$$n_1+n_2+……+n_k=n$$

以下的和式中的求和号，指对满足条件的n_1到n_k全体求和。那么，根据上文的定义，直接写出：

$$s_1(n,k)={(-1)}^n\frac{n!}{k!}\sum \frac{1}{n_1n_2……n_k}$$

$$S_2(n,k)=\frac{n!}{k!}\sum \frac{1}{n_1!n_2!……n_k!}$$

我们根据定义式就能清楚看出，第一类Stirling数的绝对值增长速度，比第二类Stirling数增长速度快。因为相同求和条件下相似的式子，第二类分母中是阶乘，而第一类是简单的数本身。

对于第二类Stirling数，自然可以配成多项式定理中的系数，可以联系多项式定理，最后可以解出这个较为简单的式子：

$$S_2(n,k)=\frac{1}{k!}\sum_{j=0}^k C_k^j j^n{(-1)}^{k-j}$$

对于第一类Stirling数，没有解决办法。例如特例第二列，它恰好是调和级数部分和的分子（约分前）。记Hn是第n个调和级数部分和：

$$H_n=\sum_{i=1}^n \frac{1}{i}$$

就有：

$$s_1(n,2)={(-1)}^n (n-1)!H_{n-1}$$

如果利用下文的递推式，强行推广至负下标，会得到这样的结论：

$$s_1(n,k)={(-1)}^{n+k}S_2(-k,-n)$$

和组合数一样，在数表中Stirling数也由左上角的数和正上方的数求和得到。

但是，Stirling数都是“右倾”的，即从正上方继承的数前方都带有一个系数，而左上方没有。具体的写就是：

第一类Stirling数继承了上方数的行数，带绝对值的时候是简单的求和，不带时要加负号：

$$s_1(n,k)=s_1(n-1,k-1)-(n-1)s_1(n-1,k)$$

第二类Stirling数继承了列数：

$$S_2(n,k)=S_2(n-1,k-1)+kS_2(n-1,k)$$

这两个递推式是最重要的公式。

虽然每一列的通项难以解出，但是斜线方向的通项总是多项式量级的，利用数学归纳法就可以解出来。最边上的斜线全是1，内侧的斜线是简单的自然数和（第二类为正，第一类为负）。用组合恒等式可以递推地算出再往内侧的斜线：

$$s_1(n,n-2)=3C_n^4+2C_n^3$$

$$S_2(n,n-2)=3C_n^4+C_n^3$$

$$s_1(n,n-3)=-15C_n^6-20C_n^5-6C_n^4$$

$$S_2(n,n-3)=15C_n^6+10C_n^5+C_n^4$$

$$s_1(n,n-4)=105C_n^8+210C_n^7+130C_n^6+24C_n^5$$

$$S_2(n,n-4)=105C_n^8+105C_n^7+25C_n^6+C_n^5$$

可见，第t条斜线一定构成t-2次多项式，并且两类Stirling数的首项系数相同或相反（都是奇数的双阶乘）。

因为上面列出的数表都是下三角形矩阵，所以对于每一行，长度都是有限的，而对于每一列，长度都是无限的。如果配上两个变元x与y，就能写出二元的生成函数。

先看Bell数，Bell数是同行（固定n，对全体k求和）第二类Stirling数的和。对于Bell数，有指数型生成函数。指数型生成函数就是每项下面要配一个阶乘，就像指数的展开式一样：

$$B(x)=\sum_{n=0}^{\infty} \frac{B_n}{n!}x^n=e^{e^x-1}$$

展开成第二类Stirling数，就有以下两个式子：

$$\sum_{n=0}^{\infty} \sum_{k=0}^{\infty} \frac{S_2(n,k)}{n!}x^ny^k=e^{y(e^x-1)}$$

$$\sum_{n=0}^{\infty} \frac{S_2(n,k)}{n!}x^n=\frac{1}{k!}{(e^x-1)}^k$$

对于第一类Stirling数，也有类似的指数型生成函数：

$$\sum_{n=0}^{\infty} \sum_{k=0}^{\infty} \frac{s_1(n,k)}{n!}x^ny^k={(1+x)}^y$$

$$\sum_{n=0}^{\infty} \frac{s_1(n,k)}{n!}x^n=\frac{1}{k!}{(\ln(1+x))}^k$$

为了方便，引入一个记号“阶乘的比”表示一种自变量为x的一元多项式：

$$\frac{x!}{(x-n)!}=x(x-1)……(x-n+1)$$

它是多项式，阶乘比只是一种形式上的记号，这里提前说明。

对于第一类Stirling数，有按行的普通生成函数，直接配上系数，没有阶乘做分母：

$$\sum_{k=0}^{n} s_1(n,k)x^k=\frac{x!}{(x-n)!}$$

通过同样手法就知道，它的绝对值的生成函数有：

$$\sum_{k=0}^{n} |s_1(n,k)|x^k=\frac{(x+n-1)!}{(x-1)!}$$

因为都包含了模p的全体零点，无论带不带绝对值都有：

$$\sum_{k=0}^{p} s_1(p,k)x^k=\frac{x!}{(x-p)!}\equiv \sum_{k=0}^{p} |s_1(p,k)|x^k=\frac{(x+p-1)!}{(x-1)!}\equiv x^p-x \mod p$$

也就是说，除了两端的第一类Stirling数，第p行中间的第一类Stirling数都被p整除。

第二类没有按行的结论，但有按列的结论：

$$\sum_{n=0}^{\infty} S_2(n,k)x^n=\frac{x^k}{(1-x)(1-2x)……(1-kx)}$$

也有同余式：

$$\sum_{n=0}^{\infty} S_2(n,p)x^n=\frac{x^p}{(1-x)(1-2x)……(1-px)}\equiv \frac{x^p}{1-x^{p-1}}\mod p$$

接下来的阐述采用了矩阵“批量处理”的观点，来解释上一节的内容。

我们给出记法，数表构成的两个n阶方阵：

$${(s_1)}_n$$

$${(S_2)}_n$$

如果没有下角标，就默认为无穷阶阵。

上面这两个方阵是互逆的，乘在一起得到单位阵：

$${(s_1)}_n{(S_2)}_n=I_n$$

因此下面的公式显然是成立的。

$$\sum_{k=1}^{n} S_2(n,k)\frac{x!}{(x-k)!}=x^n$$

$$\sum_{n=0}^{\infty}\sum_{k=0}^{n} \frac{S_2(n,k)}{n!}x^n\frac{x!}{(x-k)!}=e^{xy}$$

$$\sum_{n=0}^{\infty}\sum_{k=0}^{n} S_2(n,k)x^n\frac{x!}{(x-k)!}=\frac{1}{1-xy}$$

最后一个式子就是无穷大单位阵。

为什么互逆呢？这就要从矩阵的作用谈起。对于一元多项式F和G，如果它们之间存在着这样的关系：

$$G(x)=F(e^x-1)$$

$$F(x)=G(\ln(1+x))$$

那么，对于它们第n项的系数f_n和g_n，之间就应该满足这样的关系：

$$g_n=\sum_{k=0}^{\infty} S_2(n,k)f_k$$

$$f_n=\sum_{k=0}^{\infty} s_1(n,k)g_k$$

即原来的多项式也可以直接写出：

$$G(x)=\sum_{n=0}^{\infty} \sum_{k=0}^{\infty} S_2(n,k)f_kx^n$$

$$F(x)=\sum_{n=0}^{\infty} \sum_{k=0}^{\infty} s_1(n,k)g_kx^n$$

我们把多项式的系数看作列向量f和g，上面的等式就是熟知的矩阵左乘列向量。

$$g=(S_2)f$$

$$f=(s_1)g$$

无限大矩阵s_1和S_2的作用就很明显了。左乘一个s_1，代表将变元替换成为对数；左乘一个S_2，代表将变元替换成为指数。这就是上面绝大多数公式的统一。例如上文的指数型生成函数，以及下面的式子：

$$\sum_{n=0}^{\infty} \sum_{k=0}^{\infty} \frac{k!}{n!}s_1(n,k)x^ny^k=\frac{1}{1-y\ln(1+x)}$$

$$\sum_{n=0}^{\infty} \sum_{k=0}^{\infty} \frac{k!}{n!}S_2(n,k)x^ny^k=\frac{1}{1-y(e^x-1)}$$

运用这个结论，几乎是显然的。我们还可以借此构造更多的实例，在此就不写了。

考虑Lucas定理的证明，见素数幂次与p进数问题第七节。

$$C_{m_1p+m_2}^{n_1p+n_2}\equiv C_{m_1}^{n_1}C_{m_2}^{n_2} \mod p$$

只用到了：

$${(x+1)}^p\equiv x^p+1 \mod p$$

上文说，无论带不带绝对值都有：

$$\sum_{k=0}^{p} s_1(p,k)x^k\equiv x^p-x \mod p$$

除了两端的第一类Stirling数，第p行中间的第一类Stirling数都被p整除。

所以完全同样的可以写出第一类Stirling数与绝对值的Lucas定理：

$$\sum_{k=0}^{n_1p+n_2} s_1(n_1p+n_2,k)x^k \equiv x^{n_1}{(x^{p-1}-1)}^{n_1}\sum_{k=0}^{n_2} s_1(n_2,k)x^k=x^{n_1}\sum_{t=0}^{n_1}{(-1)}^{n_1-t}C_{n_1}^tx^{(p-1)t}\sum_{k=0}^{n_2} s_1(n_2,k)x^k \mod p$$

$$\sum_{k=0}^{n_1p+n_2} |s_1(n_1p+n_2,k)|x^k \equiv x^{n_1}{(x^{p-1}-1)}^{n_1}\sum_{k=0}^{n_2} |s_1(n_2,k)|x^k=x^{n_1}\sum_{t=0}^{n_1}{(-1)}^{n_1-t}C_{n_1}^tx^{(p-1)t}\sum_{k=0}^{n_2} |s_1(n_2,k)|x^k \mod p$$

也有第二类Stirling数按列的Lucas定理。

$$\sum_{n=k_1p+k_2}^{\infty} S_2(n,k_1p+k_2)x^n\equiv \frac{x^{pk_1}}{{(1-x^{p-1})}^{k_1}}\sum_{n=k_2}^{\infty} S_2(n,k_2)x^n=x^{pk_1}\sum_{t=0}^{\infty} C_{k_1-1+t}^{k_1-1}x^{(p-1)t}\sum_{n=k_2}^{\infty} S_2(n,k_2)x^n\mod p$$

对于第二类Stirling数，这个式子可以直接展开。记带余除法：

$$n-(k_1p+k_2)=n_1(p-1)+n_2$$

其中n_2取值为0到p-2。则有：

$$S_2(k_1p+k_2+n_1(p-1)+n_2,k_1p+k_2)\equiv\sum_{t=0}^{n_1} C_{k_1+n_1-t-1}^{k_1-1}S_2(k_2+n_2+(p-1)t,k_2)\mod p$$

这是一个较复杂的卷积式，并不是一一对应的化归，但是总之将情况化归到了0到p-1列的某一列中。

对于第一类Stirling数，显然带不带绝对值奇偶性都是一样的，乘不乘-1奇偶性也是一样的。令n_2为0或者是1：

$$\sum_{k=0}^{2n} s_1(2n,k)x^k \equiv x^{n}{(x-1)}^{n}\sum_{k=0}^{0} s_1(0,k)x^k=x^{n}\sum_{t=0}^{n}C_{n}^tx^t \mod 2$$

$$\sum_{k=0}^{2n+1} s_1(2n+1,k)x^k \equiv x^{n}{(x-1)}^{n}\sum_{k=0}^{1} s_1(1,k)x^k=x^{n+1}\sum_{t=0}^{n}C_{n}^tx^t \mod 2$$

也就是说，每一行前面一半全是偶数，后面一半与它一半的那一行组合数奇偶性相同。

对于第二类Stirling数，令k_2是0或1。由于第0列只有0的位置是1，第1列从1开始全是1，所以：

$$S_2(2k_1+n,2k_1)\equiv C_{k_1+n-1}^{k_1-1}\mod 2$$

$$S_2(2k_1+1+n,2k_1+1)\equiv\sum_{t=0}^{n} C_{k_1+t-1}^{k_1-1}=C_{k_1+n}^{k_1}\mod 2$$

接下来必须假设p不是2，即p是奇素数。由于只有第一类Stirling数有一一对应的化归，所以只研究第一类Stirling数。

二项式展开：

$$\sum_{k=0}^{n_1p+n_2} s_1(n_1p+n_2,k)x^k \equiv x^{n_1}{(x^{p-1}-1)}^{n_1}\sum_{k=0}^{n_2} s_1(n_2,k)x^k=x^{n_1}\sum_{t=0}^{n_1}{(-1)}^{n_1-t}C_{n_1}^tx^{(p-1)t}\sum_{k=0}^{n_2} s_1(n_2,k)x^k \mod p$$

$$\sum_{k=0}^{n_1p+n_2} |s_1(n_1p+n_2,k)|x^k \equiv x^{n_1}{(x^{p-1}-1)}^{n_1}\sum_{k=0}^{n_2} |s_1(n_2,k)|x^k=x^{n_1}\sum_{t=0}^{n_1}{(-1)}^{n_1-t}C_{n_1}^tx^{(p-1)t}\sum_{k=0}^{n_2} |s_1(n_2,k)|x^k \mod p$$

我们知道，n_2不超过p，即化归后到了前p-1行。原来一行的前n_1个数（0到n_1-1）都被p整除。

观察式中组合数部分。组合数部分每两项之间距离是p-1，但是后面k跑遍的部分是0到p-1，有p个数，会不会造成重叠？

不会。因为第一类Stirling数数表的形状：前p-1行中，只有第0行在第0列有数1，其余行在第0列都没有数（为0）；但是第0行，也只有在第0列有数1，在其余列都没有数。这就保证它们可以按照p-1的周期重复而不重叠。

为了方便讨论，将以上区分为第0行和1到p-1行两种情况，即整除与不整除两种情况。

当n_2等于0时：

$$\sum_{k=0}^{n_1p} s_1(n_1p,k)x^k \equiv \sum_{k=0}^{n_1p} |s_1(n_1p,k)|x^k \equiv x^{n_1}\sum_{t=0}^{n_1}{(-1)}^{n_1-t}C_{n_1}^tx^{(p-1)t} \mod p$$

即p的n_1倍数行，前n_1个数（0到n_1-1）被p整除，从第n_1个数开始后面每p-1个数中（p-1是偶数，因此奇偶性相同）才有一个不被p整除，并且与第n_1行对应的组合数（配上-1的系数）同余。即仅当k-n_1是p-1倍数时不被p整除：

$$k-n_1=k_1(p-1)$$

则有：

$$s_1(n_1p,n_1+k_1(p-1))\equiv {(-1)}^{n_1-k_1}C_{n_1}^{k_1}\mod p$$

当n_2不等于0时，前n_1个数（0到n_1-1）仍旧被p整除。于是这里认为k至少为n_1，将k-n_1（原来k属于靠右的n-n_1列）做带余除法，只是除数换成p-1，有：

$$k-n_1=k_1(p-1)+k_2$$

这里规定，k_2的取值范围是1到p-1，与通常的带余除法略有不同。由于k不超过n，而n有这个式子：

$$n-n_1=n_1(p-1)+n_2$$

这里n_2的范围是0到p-1。因此k_1不超过n_1，则有：

$$s_1(n_1p+n_2,n_1+k_1(p-1)+k_2)\equiv {(-1)}^{n_1-k_1}C_{n_1}^{k_1} s_1(n_2,k_2)\mod p$$

$$|s_1(n_1p+n_2,n_1+k_1(p-1)+k_2)|\equiv {(-1)}^{n_1-k_1}C_{n_1}^{k_1} |s_1(n_2,k_2)|\mod p$$

即从n_1开始，第k_1个连续p-1化归到了第一类Stirling数第n_2行的1到p-1位置，以及组合数的第n_1行的k_1位置。这样就完成了递归。绝对值可以去掉是因为保证了同样的奇偶性。

第一类Stirling数绝对值同行部分和余数问题。求第一类斯特林数的绝对值n行l到r项和%p。

圆神现在正在解决一个有趣的任务，它给出四个整数n，l，r和p，并询问：

$$\sum_{k=l}^r |s_1(n,k)| \mod p$$

其中p是质数。似乎圆神在一分钟内就想出了主旨。你能快点吗？

输入唯一一行包含四个整数n，l，r和p（1≤n≤10^18）0≤l≤r≤n，2≤p≤10^6，p是质数）。

输出一个表示答案的整数。

显然可以拆成两个从0开始的同行部分和的差。不妨记前m项为：

$$\sum_{k=0}^{m} |s_1(n_1p+n_2,k)|$$

这一行给定了，仍旧可以设n比p大，于是可以化归到比p小的部分：

$$n=n_1p+n_2$$

这里n_1和n_2都相当于给定了。根据上文第一类Stirling数的Lucas定理，前n_1个数全都模p余0，即当m小于n_1的时候部分和全部为0，事实上只需要观察后半部分的部分和。

首先，右边两部分可以分开求和。类似于上文的k，设m也有相关的式子：

$$m-n_1=m_1(p-1)+m_2$$

当n_2为0的时候，对m-n_1是简单的带余除法：

$$\sum_{k=0}^{m} |s_1(n_1p,k)|\equiv \sum_{k_1=0}^{m_1}{(-1)}^{n_1-k_1}C_{n_1}^{k_1}\mod p$$

当n_2不为0的时候，对m-n_1是特殊的带余除法，余数m_2取值1到p-1：

$$\sum_{k=0}^{m} |s_1(n_1p+n_2,k)|=\sum_{k_1=0}^{m_1-1}\sum_{k_2=1}^{p-1}|s_1(n_1p+n_2,n_1+k_1(p-1)+k_2)|+\sum_{k_2=1}^{m_2}|s_1(n_1p+n_2,n_1+m_1(p-1)+k_2)|\mod p$$

$$\sum_{k=0}^{m} |s_1(n_1p+n_2,k)|\equiv \sum_{k_1=0}^{m_1-1}{(-1)}^{n_1-k_1}C_{n_1}^{k_1} \sum_{k_2=1}^{p-1}|s_1(n_2,k_2)|+{(-1)}^{n_1-m_1}C_{n_1}^{m_1}\sum_{k_2=1}^{m_2}|s_1(n_2,k_2)|\mod p$$

同一行第一类Stirling数绝对值部分和，恰好是行数的阶乘。即：

$$\sum_{k=0}^{m} |s_1(n_1p+n_2,k)|\equiv n_2!\sum_{k_1=0}^{m_1-1}{(-1)}^{n_1-k_1}C_{n_1}^{k_1}+{(-1)}^{n_1-m_1}C_{n_1}^{m_1}\sum_{k_2=1}^{m_2}|s_1(n_2,k_2)|\mod p$$

这里n_2总比p要小，因此阶乘不会被消掉。最后问题的关键在组合数的部分。

对k_2和n_2进行枚举，范围仍旧都是0到p-1。因此关键在左边n_1和k_1的部分。

$${(-1)}^{n_1}\sum_{k_1=0}^{m_1-1} C_{n_1}^{k_1}{(-1)}^{k_1}$$

最后化归为简单的Lucas定理的问题，给定n_1、m_1-1、x，计算多项式取模意义下的值：

$$\sum_{k_1=0}^{m_1-1} C_{n_1}^{k_1}x^{k_1}$$

即二项式展开的部分和问题，见素数幂次与p进数问题第七节。