# Grox的序列五A：一次十进制模幂

**出题人解法：Stirling 数与下降阶乘展开。Codex（GPT-6）：将模幂组织为一次十进制求值及连续乘二，并截断不需要的 Stirling 列。** [计算程序](alternative-decimal.cpp)沿用[主题解](solution.zh.md)的计数恒等式，改变指数处理方法，不需要分解模数、欧拉函数或模逆元。

## 从最小指数向上计算

当 $k=0$ 时，按题目的零次幂约定，答案为 $2^n-1$ .直接按十进制数字计算这个幂；当 $n=0$ 时答案为零。

对 $k>0$ ，令 $m=\min(n,k)$ .主题解已证明

$$S=\sum_{j=1}^{m}S(k,j)(n)_j2^{n-j}\pmod p$$

先用滚动递推求出 $S(k,1),\ldots,S(k,m)$ .每行只需要前 $m$ 列，因为更新某列只依赖本列和前一列。再由 $n\bmod p$ 逐项相乘求下降阶乘，保存

$$W_j=S(k,j)(n)_j\bmod p$$

十进制读入时用饱和计数得到 $m$ ，对十进制串做一次小整数减法，得到非负整数 $n-m$ 的十进制表示。减法的借位可连续经过多个零，不能用指数余数代替这个真实减法。

计算 $B=2^{n-m}\bmod p$ .若已读前缀指数为 $t$ ，下一个数字为 $d$ ，则

$$2^{10t+d}=(2^t)^{10}2^d$$

按此式扫描数字即可处理任意长度的指数，不需要底数与模数互质。

最后从 $j=m$ 向 $1$ 扫描，加入 $W_jB$ 后将 $B$ 乘二。对应指数依次为 $n-m,n-m+1,\ldots,n-1$ ，全部非负。

## 正确性与边界

Stirling 有限求和式在整数中成立，滚动递推与下降阶乘给出正确的权值。十进制模幂由上述恒等式逐位保持真实指数的余数；连续乘二准确生成其他指数。因此每项都与有限求和式一致，对任意正整数模数成立。$p=1$ 单独返回零，$n=0$ 单独返回零；负的下降阶乘因子先规范再相乘，因子为零后也无需除法。

## 复杂度与取舍

设 $D$ 为十进制位数。非零分支的时间为 $O(km+D)$ ，空间为 $O(m+D)$ ；$k=0$ 或 $n=0$ 时仅需 $O(D)$ 时间。最坏 $m=k$ 时为 $O(k^2+D)$ .

Euler 指数方案需要 $O(\sqrt p)$ 的试除和逐项模幂；此方案省去这两部分及非互质指数边界，计数算法保持一致。它是一种更简洁的完整范围实现，与现有标程并列；实际时间与内存差异以同输入测量为准。

## 同输入测量

与标程在全部 10 份正式输入上的输出一致；五轮交替计时及输入、源码、程序哈希见[完整记录](../../../docs/benchmark-R14-supplements.json)，环境见[参考评测环境](../../../docs/评测环境与性能.md)。标程最慢中位耗时为 0.036134 秒，补充方案为 0.035908 秒；峰值工作集分别为 5.30 与 5.32 MiB，包含进程与运行库开销。
补充程序在全部已测正式输入上均低于 0.5 秒参考时限。该结论仅针对随附实现、这些输入与参考环境；有限测试不代替正确性证明，也不保证每一种同阶实现通过。