# Grox的序列一：出题人解法——指数生成函数与 NTT

## 计数恒等式

先在有理数上使用指数生成函数。任意次数、偶数次、零次或正奇数次分别对应 $e^x$ 、$\cosh x$ 、$1+\sinh x$ .不同符号选择位置的二项式系数，恰好由指数生成函数乘法处理。因此答案是

$$N![x^N]\ e^{ax}(\cosh x)^b(1+\sinh x)^c.$$

令 $d=2(b+c)$ ，定义

$$F(z)=(1+z^2)^b(z^2+2z-1)^c=\sum_{i=0}^{d}f_i z^i.$$

将双曲函数改写为指数函数，得到答案恒等式

$$2^{-(b+c)}\sum_{i=0}^{d}f_i(a-b-c+i)^N.$$

推导先在有理数上成立，清除二的幂分母后是整数恒等式，因此对任意大的 $N$ 仍可取模；这里没有在模域内除以 $N!$ .仅需二的逆元。第三组的零次选项产生多项式中的 $2z$ ，这个系数不能省略。

## 大指数与实现边界

逐位读入 $a\bmod p$ 和 $N\bmod(p-1)$ ，同时单独记录 $N$ 是否真正为零。对于非零底数可以用费马小定理约简指数；对于零底数，正指数的结果必须为零，而真正的零指数取一。因此，正的 $p-1$ 倍数不能当成零长度。

所有剩余先规范到 $[0,p-1]$ .乘积用 64 位整数并及时取模，因 $p^2<2^{63}$ 而安全。以下算法中参与求逆的小整数均不超过 $d<p$ .

## 计算多项式

用二项式系数得到 $A(z)=(1+z^2)^b$ ：奇数次项为零，$[z^{2i}]A=\binom bi$ .相邻系数用 $(b-i)/(i+1)$ 递推，时间线性。

从常数一开始，连续乘 $c$ 次二次式 $z^2+2z-1$ 得到 $B(z)$ .每次从高次往低次更新，避免覆盖尚需读取的系数，总时间为 $O(c^2)$ .

令 $L$ 为严格大于 $d=2(b+c)$ 的最小二次幂。将两个数组补零到 $L$ ，执行 NTT，逐点相乘，再逆变换并除以 $L$ ，获得 $F=AB$ .当 $d=0$ 时取 $L=1$ .注意次数为 $d$ 的多项式有 $d+1$ 个系数，$L=d$ 会造成首尾混叠。

模数为 $479\times2^{21}+1$ ，原根为三；本题最大变换长度为 $2^{18}$ ，可以使用所需各阶单位根。长度为 $L$ 的 NTT 将卷积变为逐点乘法，逆 NTT 恢复模域中的系数。由于乘积次数小于 $L$ ，循环卷积等于所需的普通卷积。

## 正确性与复杂度

二项式递推精确构造 $A$ ，逐次二次式乘法精确构造 $B$ ，NTT 计算其完整乘积。代入已经证明的指数和恒等式即得到答案。

设 $D$ 为输入 $a,N$ 的十进制字符总数，时间为 $O(D+b+c^2+L\log L+(d+1)\log p)$ ，空间为 $O(D+L+b)$ .程序 [alternative.cpp](alternative.cpp) 支持完整范围；[四项递推](solution.zh.md)省去二次展开和卷积，作为首选。

出题人解法贡献了生成函数和 NTT 路线；GPT-6 提供完整推导与标准 C++17 实现，补全零次选项、变换长度及零指数边界。两种程序经组合 DP、独立三项式展开与正式压力数据核对，性能见[记录](../../../docs/benchmark-R24.json)。