# Grox的序列五B：指数生成函数

**Codex（GPT-6）：应用二项式矩的指数生成函数与形式幂级数 log/exp。** 生成函数、Newton 迭代与 NTT 都是已有通用方法，不将它们归为本题原创。[计算程序](alternative-fps.cpp)与[Stirling 卷积标程](solution.zh.md)的推导明显不同；后者运算更少，并能截断到所需项，仍作为首选。

## 直接提取矩

对 $k>0$ ，形式指数函数给出

$$\sum_{i=0}^n\binom ni e^{iz}=(1+e^z)^n$$

因此所求为

$$S=k!\,[z^k](1+e^z)^n$$

这里 $[z^k]$ 表示取第 $k$ 次项系数。取该系数时，零下标项的正次幂为零，符合题意；$k=0$ 则单独返回 $2^n-1$ ，不能直接使用生成函数的常数项。

将常数项规范为一：

$$H(z)=\frac{1+e^z}{2},\qquad H(0)=1,\qquad (1+e^z)^n=2^n\exp\big(n\log H(z)\big)$$

构造 $e^z$ 的前 $k+1$ 项，即逆阶乘，求 $F=n\log H$ ，再求 $G=\exp F$ .答案为 $2^n k!G_k$ .全过程只保留次数不超过 $k$ 的项。

## 形式级数的实现

逆元使用精度倍增：若 $AU=1\pmod{z^m}$ ，则

$$U_{\mathrm{next}}=U(2-AU)\pmod{z^{2m}}$$

因为新误差是旧误差的平方，精度翻倍。对常数项为一的级数，用

$$\log A=\int\frac{A'}A\,dz$$

并取积分常数为零。若 $G=\exp F\pmod{z^m}$ ，则

$$G_{\mathrm{next}}=G(1+F-\log G)\pmod{z^{2m}}$$

误差 $F-\log G$ 从第 $m$ 次项开始，修正的一阶项消去该误差；二阶项从第 $2m$ 次项开始，故新精度成立。所有乘法使用 NTT 或固定小规模朴素乘法。

## 正确性与适用条件

二项式定理给出生成函数，指数函数的第 $k$ 项系数恰为正次幂除以 $k!$ .规范常数项后的 log/exp 恒等式保持同一形式级数；精度倍增迭代准确恢复所需系数，乘回 $2^n k!$ 即得到答案。

固定质数 $P=1005060097$ 下，$k<P$ ，逆阶乘、积分中的整数分母及 $2$ 的逆元均存在。级数逆元的常数项非零；log 输入的常数项为一，exp 输入的常数项为零。最大 NTT 长度为 $2^{18}$ ，能整除 $P-1$ .不把这套含除法的程序直接用于五 A 的任意合数模数。

## 复杂度与取舍

精度倍增各层的代价是几何递增的多项式乘法之和，总时间 $O(k\log(k+1)+\log(n+1))$ ，空间 $O(k+1)$ .渐进阶与未截断的 Stirling 卷积相同，但多次级数求逆、log 与 exp 带来更大常数。首选方案在 $m=\min(n,k)$ 很小时还可明显减少工作。此方案提供不同的完整推导与程序；是否满足当前时限以实测为准，不能仅凭渐进阶相同断言通过。

## 同输入测量

与标程在全部 10 份正式输入上的输出一致；五轮交替计时及输入、源码、程序哈希见[完整记录](../../../docs/benchmark-R14-supplements.json)，环境见[参考评测环境](../../../docs/评测环境与性能.md)。标程最慢中位耗时为 0.124843 秒，补充方案为 0.637622 秒；峰值工作集分别为 9.89 与 14.93 MiB，包含进程与运行库开销。
补充程序在用例 04, 05, 06, 07, 08, 09 的中位耗时超过 0.5 秒参考时限，因此当前实现为**备用方案，不能通过已测完整数据的当前时限**。算法正确性与运行时限分别说明，不能将它作为当前标程。