题解：P14654 夤生月

· · 题解

建议升蓝

看到了著名 OI 金牌选手脚厮鸢的题目放到了主题库上，我本来已经AFO了，又爬起来写一篇题解。

焦老师真是太牛了，我对你的敬仰如高山流水般连绵不绝！！你的伟大荡去了我内心的苦涩，你是我的偶像啊！！

无符号第一类斯特林数

无符号第一类斯特林数\begin{bmatrix}n\\m\end{bmatrix}（也记为S_1(n,m)）的组合意义是：将 n 个有标号元素的排列划分为 m 个非空环（连通块) 的方案数。

其生成函数是上升阶乘的展开式:

x^{\overline{n}} = x(x+1)(x+2)\cdots(x+n-1) = \sum_{k=0}^n \begin{bmatrix}n\\k\end{bmatrix} x^k
我们通过生成函数的模2化简推导结论：

上升阶乘 x(x+1)\cdots(x+n-1) 的因子中，i 取 0 \sim n-1（共 n 个因子）：

因此模2下上升阶乘可化简为：

x^{\overline{n}} \equiv x^{\lceil \frac{n}{2} \rceil} \cdot (x+1)^{\lfloor \frac{n}{2} \rfloor} \pmod{2}

用二项式定理展开 (x+1)^{\lfloor \frac{n}{2} \rfloor} ，再与 x^{\lceil \frac{n}{2} \rceil} 相乘：

x^{\lceil \frac{n}{2} \rceil} \cdot (x+1)^{\lfloor \frac{n}{2} \rfloor} = x^{\lceil \frac{n}{2} \rceil} \cdot \sum_{k=0}^{\lfloor \frac{n}{2} \rfloor} \binom{\lfloor \frac{n}{2} \rfloor}{k} x^k = \sum_{k=0}^{\lfloor \frac{n}{2} \rfloor} \binom{\lfloor \frac{n}{2} \rfloor}{k} x^{\lceil \frac{n}{2} \rceil + k}

要得到 x^m 的系数（即 \begin{bmatrix}n\\m\end{bmatrix} \mod 2 ），需满足 \lceil \frac{n}{2} \rceil + k = m ，即 k = m - \lceil \frac{n}{2} \rceil 。

因此：

\begin{bmatrix}n\\m\end{bmatrix} \equiv \binom{\lfloor \frac{n}{2} \rfloor}{m - \lceil \frac{n}{2} \rceil} \pmod{2}

根据卢卡斯定理在 p=2 时的推论：

二项式系数 \binom{a}{b} \mod 2 = 1 ，当且仅当 b 的二进制是 a 的二进制的子集（即 b \& a = b ）

第二类斯特林数

第二类斯特林数 \begin{Bmatrix}n\\m\end{Bmatrix}（也记为S_2(n,m) ）的组合意义是：将 n 个有标号元素划分为 m 个非空无标号集合的方案数。

其核心递推关系为：

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

边界条件：

递推式的模2简化

其形式与组合数的递推式（ \binom{a}{b} = \binom{a-1}{b} + \binom{a-1}{b-1} ）高度匹配。

通过归纳法我们可以证明结论：

\begin{Bmatrix}n\\m\end{Bmatrix} \equiv \binom{n-1 - \lfloor \frac{m}{2} \rfloor}{\lfloor \frac{m}{2} \rfloor - 1} \pmod{2}

然后应用卢卡斯和上面一样，于是就做完了。

注意边界条件：如果 m=0 且 n>0 或者 m>n 答案为 0。