如何在可接受时间内计算大斯特林数S(114514,100)？

核心思路：针对性利用容斥公式+高效大数运算 #

当k远小于n时（这里k=100，n=114514），直接用常规递推效率极低，改用第二类斯特林数的容斥公式是最优选择：

S(n,k) = (1/k!) × Σ_{i=0到k} (-1)^(k-i) × C(k,i) × i^n

这个公式的计算量仅围绕k=100展开，而非n=114514，能把复杂度从O(nk)降到O(k log n)，大幅缩短计算时间。

具体实现步骤 #

1. 预计算组合数C(k,i)
   k=100很小，直接用递推公式C(k,i) = C(k,i-1) × (k-i+1)/i，或通过阶乘公式C(k,i) = k!/(i!×(k-i)!)计算，现代大数库能轻松处理这些数值。

2. 快速计算i^n
   对i^114514采用二进制快速幂算法，时间复杂度为O(log n)，单次计算仅需毫秒级时间。

3. 大数约分与求和
   计算求和项时，先对每一项与k!（100!）进行约分，避免处理过大的中间数；或用支持分数运算的大数库直接计算，最后转换为整数。

工具与代码示例（Python） #

推荐用gmpy2库处理大数运算，比Python内置int效率更高：

import math
from gmpy2 import mpz, fac

def stirling2(n, k):
    k_fact = fac(k)
    total = mpz(0)
    for i in range(k + 1):
        sign = (-1) ** (k - i)
        comb = math.comb(k, i)
        power = mpz(i) ** n
        total += sign * comb * power
    return total // k_fact

# 计算并保存结果（位数过多，直接写入文件）
result = stirling2(114514, 100)
with open("stirling_result.txt", "w") as f:
    f.write(str(result))

安装gmpy2：pip install gmpy2，如果没有该库，用Python内置int也可运行，只是速度稍慢，但仍能在几分钟内完成计算。

为什么之前的工具效率低？ #

Mathematica、Maple的默认斯特林数函数采用通用算法，未针对k远小于n的场景优化；Scipy对超大数的支持不足且算法复杂度高。而上述方法针对性利用容斥公式，效率提升数个数量级，无需更换设备，普通消费级CPU即可完成计算。

内容的提问来源于stack exchange，提问作者youthdoo