# 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)$ 为下降阶乘。恒等式

$$i^k=\sum_{j=0}^k S(k,j)(i)_j$$

可以按函数的不同取值数计数：将 $k$ 个标号对象分成 $j$ 个非空原像组，再为这些组指定 $j$ 个不同的目标。于是

$$\binom ni(i)_j=(n)_j\binom{n-j}{i-j}$$

交换求和顺序后，由二项式定理得到

$$\sum_{i=0}^n i^k\binom ni=\sum_{j=1}^{\min(n,k)}S(k,j)(n)_j2^{n-j}$$

这里 $S(k,0)=0$ ，且 $j>n$ 的下降阶乘为零。显式使用 $\min(n,k)$ 可以避免构造负指数。

## Stirling 递推与合数模数

使用

$$S(t,j)=jS(t-1,j)+S(t-1,j-1)$$

初始 $S(0,0)=1$ ，其他项为零。每行从大下标向小下标更新，只保留一行，时间 $O(k^2)$ 、空间 $O(k)$ .出题人使用完整表格保存同一递推，空间为 $O(k^2)$ ；滚动数组没有更换计数算法。

下降阶乘直接逐项相乘对 $p$ 取模，不能把它改为含模逆元的阶乘比，因为 $p$ 可以为合数。

令 $\phi=\varphi(p)$ .对非负指数 $e$ ，计算 $2^e\bmod p$ 时使用

$$\widehat e=\begin{cases}e,&e<\phi\\e\bmod\phi+\phi,&e\ge\phi\end{cases}$$

这对偶数模数也成立：对 $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 列截断到所需范围；作为更简洁的完整范围实现并列介绍。

[完整题解与测量](solution-alternative-decimal.zh.md) · [计算程序](alternative-decimal.cpp)