Grox的序列一：出题人解法——指数生成函数与 NTT¶
计数恒等式¶
先在有理数上使用指数生成函数。任意次数、偶数次、零次或正奇数次分别对应 \(e^x\) 、\(\cosh x\) 、\(1+\sinh x\) .不同符号选择位置的二项式系数，恰好由指数生成函数乘法处理。因此答案是
令 \(d=2(b+c)\) ，定义
将双曲函数改写为指数函数，得到答案恒等式
推导先在有理数上成立，清除二的幂分母后是整数恒等式，因此对任意大的 \(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 支持完整范围；四项递推省去二次展开和卷积，作为首选。
出题人解法贡献了生成函数和 NTT 路线；GPT-6 提供完整推导与标准 C++17 实现，补全零次选项、变换长度及零指数边界。两种程序经组合 DP、独立三项式展开与正式压力数据核对，性能见记录。