GitHub 源文件 Markdown English

Grox的序列一：多项式系数递推

计数恒等式

先在有理数上使用指数生成函数。任意次数、偶数次、零次或正奇数次分别对应 \(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\) .

四项递推

不必先做多项式卷积。对 \(F\) 求导并清除分母，得到 \(QF'=RF\) ，其中

\[ Q=z^4+2z^3+2z-1, \]

\[ R=(2b+2c)z^3+(4b+2c)z^2+(-2b+2c)z+2c. \]

比较 \(z^k\) 的系数，令负下标系数为零，得到

\[ \begin{aligned}(k+1)f_{k+1}={}&(2k-2c)f_k+(2b-2c)f_{k-1}\\&+(2k-4-4b-2c)f_{k-2}+(k-3-2b-2c)f_{k-3}.\end{aligned} \]

从 \(f_0=(-1)^c\) 开始，预处理一到 \(d\) 的逆元，依次求出所有系数，立即累加答案。只保留最近四个系数即可。

正确性

生成函数恒等式已经证明系数加权和等于合法序列数。\(Q\) 的常数项为负一，且每个 \(k+1\) 在模域中可逆，所以该微分方程与常数项唯一确定每个后继系数。递推由逐项比较精确得到，故其生成的系数就是 \(F\) 的系数。结合对零底数和零指数的分别处理，程序计算的加权和适用于所有输入。

复杂度与方案选择

设 \(D\) 为输入 \(a,N\) 的十进制字符总数。时间为 \(O(D+(d+1)\log p)\) ，额外空间为 \(O(D+d)\) ，其中逆元表占线性空间；指数快速幂是主要计算部分。

出题人解法使用同一指数生成函数恒等式，再展开两个多项式并通过数论变换求卷积。其完整推导、正确性与实现见 NTT 解法及 alternative.cpp。它需要 \(O(D+b+c^2+L\log L+(d+1)\log p)\) 时间和 \(O(D+L+b)\) 空间，\(L\) 是严格大于 \(d\) 的最小二次幂。两个方案均可通过完整数据。

首选 std.cpp 用四项递推省去二次的展开与卷积，并减少存储；这种改进改变系数求法，指数生成函数建模仍来自出题人解法。原方法的系数展开与 NTT 更便于推广到不同的多项式乘积，作为完整补充保留。实测见性能记录。

贡献与验证

出题人解法：指数生成函数、指数和表达式、NTT 卷积。GPT-6：微分恒等式的四项递推、证明、两份标准 C++17 实现及边界修复。小规模用逐个符号选择位置的组合 DP 核对，正式数据另用三项式展开与独立 NTT 实现核对，覆盖零类型、零长度、模数倍数与次数为二次幂的情况。