GitHub 源文件 Markdown English

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

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

直接提取矩

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