# 某不科学的下降阶乘与二项式求和 — 常数空间：直接乘积与 Wilson 补集

Codex（GPT-6）：结合下降阶乘恒等式与 Wilson 定理，提供无需检查点表的[常数空间程序](alternative.cpp)。它具有明确的存储优势，但最坏时间高于标准方案；完整压力数据会超过参考时限。

沿用[主解](solution.zh.md)证明的 $n^{\underline{k}}2^{n-k}$ .当 $k>n$ 时直接返回零。否则直接相乘 $n-k+1,\ldots,n$ 需要 $k$ 次乘法。

另一边，Wilson 定理给出 $(P-1)!\equiv-1\pmod P$ .把完整阶乘分成三个不重叠区间，得到

$$
\left(\prod_{i=n-k+1}^{n}i\right)
\left(\prod_{i=1}^{n-k}i\right)
\left(\prod_{i=n+1}^{P-1}i\right)\equiv-1\pmod P
$$

因此目标下降阶乘也等于后两个区间乘积的负逆元。后两个区间共含 $P-1-k$ 个因子，所有因子都在 $[1,P-1]$ ，逆元必定存在。选择更短的一边计算，再乘上 $2^{n-k}$ .

时间为 $O(\min(k,P-1-k)+\log P)$ ，额外空间为 $O(1)$ ；若 $k>n$ 则为 $O(1)$ .这两种表达来自同一阶乘分解，所以分支选择不影响正确性。该方法适用于短乘积或接近完整模数区间的乘积，也便于核验检查点法。对于 $k$ 接近 $P/2$ ，仍需约五亿次模乘，不能用于满足当前完整时限。数据规模、五次实测和标准时限均见[性能记录](../../../docs/benchmark-R36.json)。