Grox的序列五B 题解¶
出题人解法：卷积计算第二类 Stirling 数的一行，再计算二项式矩。 Codex（GPT-6）整理 NTT、阶乘逆元、零次幂与规范余数，并将卷积截断到实际参与求和的前缀。模数固定为 \(P=1005060097\) ，与序列四、七不同。
二项式矩¶
当 \(k=0\) 时答案为 \(2^n-1\) ；当 \(k>0\) 时，使用下降阶乘展开：
这里 \(S(k,j)\) 为第二类 Stirling 数，\((n)_j=n(n-1)\cdots(n-j+1)\) .证明与序列五 A相同：按不同取值数展开 \(i^k\) ，再使用 \(\binom ni(i)_j=(n)_j\binom{n-j}{i-j}\) 和二项式定理。
用一次卷积计算需要的前缀¶
对函数的缺失目标使用容斥，得到
令 \(m=\min(n,k)\) .只构造
普通卷积的第 \(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+1)\) ；最坏情形与出题人的整行方案相同，为 \(O(k\log(k+1)+\log(n+1))\) 时间、\(O(k+1)\) 空间。当 \(n\) 很小时只需较短卷积。逐行 Stirling 递推也正确，但时间 \(O(k^2)\) ，适合较小的 \(k\) .
补充解法¶
指数生成函数直接提取二项式矩，经形式级数 log/exp 得到同阶的不同算法。它需要更多多项式运算；当前随附实现超过 0.5 秒时限，明确作为备用方案，不能作为完整数据的标程。