# 题解：某不科学的下降阶乘与二项式求和

Codex（GPT-6）：应用下降阶乘恒等式，使用固定模数的阶乘检查点实现求值，并补充常数空间的 Wilson 补集方案。恒等式、费马小定理与 Wilson 定理均为已有数学方法。

## 组合恒等式

从 $n$ 个物品中先选一个子集，再从中按顺序选出 $k$ 件指定物品。如果子集大小为 $i$ ，方案数为 $\binom ni i^{\underline{k}}$ .

也可以先从全部物品中选出有顺序的 $k$ 件，有 $n^{\underline{k}}$ 种方式；其余 $n-k$ 件独立决定是否进入子集，各有两种选择。这两种顺序描述同一组对象，因此当 $k\le n$ 时

$$\sum_{i=1}^{n}\binom ni i^{\underline{k}}=n^{\underline{k}}2^{n-k}$$

当 $k>n$ 时，每项都为零。题目保证 $k\ge1$ ，所以不需要补入 $i=0$ 项。

## 固定模数阶乘检查点（首选）

因为 $n<P$ ，所有需要的阶乘均非零，故

$$n^{\underline{k}}=\frac{n!}{(n-k)!}\pmod P$$

取块长 $B=10^6$ ，保存 $F_j=(jB)!\bmod P$ ，包括零阶乘。计算任意 $x!$ 时，从 $F_{\lfloor x/B\rfloor}$ 开始，再乘当前块中的剩余因子，最多 $B-1$ 次。逆元使用费马小定理 $a^{-1}=a^{P-2}$ .

[检查点表](factorial-table.hpp)是固定模数的计算资源，不是任意输入答案表。[生成程序](tests/generate-table.cpp)依次乘入全部因子，每到块边界输出一个常量，并检查 $(P-1)!\equiv-1\pmod P$ .它可以完全重建头文件。

生成全部检查点需要离线 $O(P)$ 时间、$O(P/B)$ 输出空间。单次输入的在线时间为 $O(B+\log P)$ ，表空间为 $O(P/B)$ .这项离线代价不能算作零；本方案适用于题目固定模数及给定上界，不声称能同样快速处理任意新模数。

## 正确性与实现

检查点由阶乘递推得到。块内继续乘剩余整数得到精确阶乘；分母可逆，费马求逆得到下降阶乘；乘以 $2^{n-k}$ 后由组合恒等式得到所求值。所有模乘使用 64 位整数，中间值小于 $P^2$ .

[标准程序](std.cpp)选择检查点法，以缩短最大规模的在线计算。[常数空间方案](solution-alternative.zh.md)及其[程序](alternative.cpp)不存储检查点，对较短乘积很方便，空间更少；中间长度的乘积耗时较多，属于完整时限之外的取舍方案。两者在正式文件上输出一致，适用时间范围见[性能记录](../../../docs/benchmark-R36.json)。

验证包含小范围逐项原式求和、随机短乘积、每一百万项区间按反方向重算的[表校验程序](tests/verify-table.cpp)，以及 Wilson 尾段核验。参见[生成与验证说明](tests/README.md)。