Grox的序列五A 题解¶
出题人解法：第二类 Stirling 数、下降阶乘与模幂。 Codex（GPT-6）补齐非互质模数的指数边界、零次幂分支，并将同一 Stirling 递推改为滚动数组。没有使用合数模数下不存在的阶乘逆元。
把巨大求和变为有限求和¶
先单独处理 \(k=0\) ：由于本题规定零的零次幂为零，答案是 \(2^n-1\) ，包括 \(n=0\) 时答案为零。
对 \(k>0\) ，令 \(S(k,j)\) 为第二类 Stirling 数，\((n)_j=n(n-1)\cdots(n-j+1)\) 为下降阶乘。恒等式
可以按函数的不同取值数计数：将 \(k\) 个标号对象分成 \(j\) 个非空原像组，再为这些组指定 \(j\) 个不同的目标。于是
交换求和顺序后，由二项式定理得到
这里 \(S(k,0)=0\) ，且 \(j>n\) 的下降阶乘为零。显式使用 \(\min(n,k)\) 可以避免构造负指数。
Stirling 递推与合数模数¶
使用
初始 \(S(0,0)=1\) ，其他项为零。每行从大下标向小下标更新，只保留一行，时间 \(O(k^2)\) 、空间 \(O(k)\) .出题人使用完整表格保存同一递推，空间为 \(O(k^2)\) ；滚动数组没有更换计数算法。
下降阶乘直接逐项相乘对 \(p\) 取模，不能把它改为含模逆元的阶乘比，因为 \(p\) 可以为合数。
令 \(\phi=\varphi(p)\) .对非负指数 \(e\) ，计算 \(2^e\bmod p\) 时使用
这对偶数模数也成立：对 \(p\) 的奇素数幂因子，\(2\) 可逆且 \(\phi\) 是对应 Euler 函数值的倍数；对二次幂因子 \(2^v\) ，当 \(e\ge\phi\) 时两个指数都至少为 \(v\) ，余数均为零。中国剩余定理合并这些结果。\(p=1\) 单独返回零。
读取十进制 \(n\) 时保存 \(n\bmod p\) 、\(n\bmod\phi\) ，以及 \(\min(n,\phi+k)\) .最后一个量允许准确判断每个 \(n-j\) 是否至少为 \(\phi\) ，也允许处理 \(n<k\) .不能在知道 \(n\ge\phi\) 后直接认定所有 \(n-j\ge\phi\) .
\(k=0\) 的分支可直接按十进制数字计算模幂：已有前缀指数为 \(t\) 、新数字为 \(d\) 时，从 \(2^t\) 更新为 \((2^t)^{10}2^d\) .这样不需要对非互质指数作特殊推断。
正确性与复杂度¶
有限求和恒等式在整数中成立；Stirling 递推、下降阶乘和安全指数计算分别给出每个因子的正确余数，所以按模数相乘相加得到答案。所有负余数都规范到最小非负代表元。
设 \(D\) 为输入 \(n\) 的十进制位数。试除分解 \(p\) 求 Euler 函数用 \(O(\sqrt p)\) 时间；总时间 \(O(k^2+k\log p+\sqrt p+D)\) ，空间 \(O(k+D)\) .\(n=10^{1000}\) 恰有 \(1001\) 位，读入容器必须容纳这一边界。
补充解法¶
沿用 Stirling 展开，直接从十进制串计算 \(2^{n-\min(n,k)}\) ，再连续乘二得到其余非负指数，省去模数分解、Euler 函数及逐项模幂。最坏时间 \(O(k^2+D)\) ，也可将 Stirling 列截断到所需范围；作为更简洁的完整范围实现并列介绍。