# Grox的序列五B 题解

**出题人解法：卷积计算第二类 Stirling 数的一行，再计算二项式矩。** Codex（GPT-6）整理 NTT、阶乘逆元、零次幂与规范余数，并将卷积截断到实际参与求和的前缀。模数固定为 $P=1005060097$ ，与序列四、七不同。

## 二项式矩

当 $k=0$ 时答案为 $2^n-1$ ；当 $k>0$ 时，使用下降阶乘展开：

$$\sum_{i=0}^n i^k\binom ni=\sum_{j=1}^{\min(n,k)}S(k,j)(n)_j2^{n-j}$$

这里 $S(k,j)$ 为第二类 Stirling 数，$(n)_j=n(n-1)\cdots(n-j+1)$ .证明与[序列五 A](../grox-sequence-5a/solution.zh.md)相同：按不同取值数展开 $i^k$ ，再使用 $\binom ni(i)_j=(n)_j\binom{n-j}{i-j}$ 和二项式定理。

## 用一次卷积计算需要的前缀

对函数的缺失目标使用容斥，得到

$$S(k,j)=\frac1{j!}\sum_{t=0}^j(-1)^{j-t}\binom jt t^k=\sum_{t=0}^j\frac{t^k}{t!}\frac{(-1)^{j-t}}{(j-t)!}$$

令 $m=\min(n,k)$ .只构造

$$U_t=\frac{t^k}{t!},\qquad W_t=\frac{(-1)^t}{t!}\qquad(0\le t\le m)$$

普通卷积的第 $j$ 项就是 $S(k,j)$ .当 $j\le m$ 时，构成这一项的两个下标都不超过 $j$ ，所以截断不丢失任何需要的项。出题人计算到 $k$ 的整行同样正确；当 $n<k$ 时，后面的列不参与最终求和，可以省去。这里仅在 $k>0$ 时卷积，因而 $t=0$ 的幂为零；$n=0$ 时直接返回零。

$P=1917\times2^{19}+1$ 是质数，$5$ 是原根。阶乘下标不超过 $m<P$ ，逆元存在。NTT 长度取严格大于 $2m$ 的最小二次幂，最大为 $2^{18}$ ，能整除 $P-1$ .先求 $m!$ 的一个逆元，再向下求出全部逆阶乘。

随后逐项更新 $(n)_j$ ，并从 $2^n$ 开始，每次乘以 $2$ 的逆元得到 $2^{n-j}$ ，只遍历 $1\le j\le m$ .所有结果规范到 $[0,P-1]$ .

## 正确性与复杂度

容斥式正确计数到 $j$ 个目标的满射，并除以目标排列数得到 Stirling 数。NTT 计算普通卷积，截断保留全部参与答案的系数；代入二项式矩恒等式即得到答案。

构造模幂需 $O(m\log(k+1))$ 时间，卷积需 $O(m\log(m+1))$ 时间，求 $2^n$ 需 $O(\log(n+1))$ 时间。总时间

$$O(m\log(k+1)+m\log(m+1)+\log(n+1))$$

空间为 $O(m+1)$ ；最坏情形与出题人的整行方案相同，为 $O(k\log(k+1)+\log(n+1))$ 时间、$O(k+1)$ 空间。当 $n$ 很小时只需较短卷积。逐行 Stirling 递推也正确，但时间 $O(k^2)$ ，适合较小的 $k$ .

## 补充解法

指数生成函数直接提取二项式矩，经形式级数 log/exp 得到同阶的不同算法。它需要更多多项式运算；当前随附实现超过 0.5 秒时限，明确作为备用方案，不能作为完整数据的标程。

[完整题解与测量](solution-alternative-fps.zh.md) · [计算程序](alternative-fps.cpp)