线性递推与阶乘逆元：从理论推导到组合数学高效应用

1. 逆元从费马小定理到线性递推第一次接触逆元这个概念时我正被一道组合数学题卡住。题目要求计算大数阶乘的模逆元用传统的费马小定理方法直接超时。后来才发现线性递推法才是解决这类问题的银弹。什么是逆元简单说就是模运算中的倒数。比如在模7的世界里3的逆元是5因为3×515≡1 mod 7。传统求逆元主要有两种方法扩展欧几里得算法适合单个数的逆元求解费马小定理当模数是质数时a^(p-2)就是a的逆元但遇到需要批量计算1到n的逆元时这两种方法的时间复杂度都是O(nlogn)当n达到1e7量级时就力不从心了。这时候就需要线性递推公式登场inv[i] (p - p//i * inv[p%i] % p) % p这个公式的神奇之处在于它把看似独立的逆元计算转化为递推关系。就像多米诺骨牌一样只要推倒第一块inv[1]1后面的都会自动倒下。实测在n1e7时线性方法比费马小定理快10倍以上。2. 线性递推的数学魔法我第一次看到这个递推公式时完全懵了——为什么p//i和p%i能组合出逆元让我们拆解这个数学魔术设tp//ikp%i根据定义有p i×t k在模p下i×t ≡ -k两边乘以inv[i]×inv[k]t×inv[k] ≡ -inv[i]最终得到inv[i] ≡ -t×inv[k] ≡ -(p//i)×inv[p%i]这个推导过程中最精妙的是模运算的等价变形。就像解魔方需要特定公式这里通过引入辅助变量t和k把复杂的逆元关系转化为已知量的组合。实际编码时要注意两个细节初始化inv[1]必须设为1这是递推的起点负数处理公式中的负号要通过加p再取模来消除ll inv[MAXN]; void pre_inv(int n, int p) { inv[1] 1; for(int i2; in; i) { inv[i] (p - p/i * inv[p%i] % p) % p; } }3. 阶乘逆元组合数学的加速器在计算组合数C(n,k) n!/(k!(n-k)!)时直接计算会遇到大数阶乘的除法问题。这时候阶乘逆元就派上用场了——我们可以预先计算好1!到n!的逆元。传统方法是为每个阶乘单独求逆元时间复杂度O(nlogn)。但利用线性递推阶乘性质可以优化到O(n)先用线性递推求出1~n的逆元数组inv计算阶乘逆元fac_inv[i] fac_inv[i1]×(i1)%p# 预处理阶乘及其逆元 fac[0] 1 for i in range(1, n1): fac[i] fac[i-1] * i % MOD fac_inv[n] pow(fac[n], MOD-2, MOD) # 费马小定理求最后一项 for i in range(n-1, -1, -1): fac_inv[i] fac_inv[i1] * (i1) % MOD这个技巧在组合数预处理中非常实用。比如当n1e6时传统方法需要约20秒而线性方法仅需0.3秒。我在Codeforces的一场比赛中就靠这个优化成功AC了一道D题。4. 实战中的坑与技巧在实际应用时我踩过几个典型的坑模数非质数线性递推要求模数与i互质一般题目都会给出质数模数数组越界预处理时要确保数组大小足够建议开n10的空间初始化遗漏忘记设置inv[1]1会导致整个递推错误对于更复杂的场景比如同时需要普通逆元和阶乘逆元可以这样优化内存vectorll inv_fac(n1); vectorll inv(n1); void pre_all(int n, int p) { inv[1] fac[1] inv_fac[1] 1; for(int i2; in; i) { inv[i] (p - p/i * inv[p%i] % p) % p; fac[i] fac[i-1] * i % p; inv_fac[i] inv_fac[i-1] * inv[i] % p; } }这个模板在我的算法竞赛生涯中出场率极高特别是在需要快速计算组合数的问题上。记住这些技巧下次遇到类似问题时就能游刃有余了。