GitHub 源文件 Markdown English

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

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

沿用主解证明的 \(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\) ，仍需约五亿次模乘，不能用于满足当前完整时限。数据规模、五次实测和标准时限均见性能记录。