记一种神秘线性求逆元方法

fzs7 · 2025-10-17 09:13:42 · 休闲·娱乐

我觉得朴素的线性求逆元方法不怎么好记，故开发了某种神秘算法来求这个东西。

我们知道，阶乘逆元是可以 O(n) 求的，设 f(i)=\frac{1}{i!} \mod p，则我们可以先求出 n!，然后用快速幂求出 f(n)，而我们注意到 f(i)=f(i+1)*(i+1)，然后阶乘逆元就 O(n) 求出来了，然后我们还发现一个东西就是 \frac{1}{i} \mod p = (i-1)!f(i) \mod p，注意到阶乘已经处理过了，直接算就行了。

代码

//_pow表阶乘,_inv表阶乘逆元,inv表逆元,V为值域,p为模数 
    _inv[0] = _pow[0] = inv[0] = 1;
    for (int i = 1; i <= V; i++) _pow[i] = _pow[i - 1] * i % p;
    _inv[V] = qpow(_pow[V]), inv[V] = _inv[V] * _pow[V - 1] % p;
    for (int i = V - 1; i >= 1; i--) _inv[i] = _inv[i + 1] * (i + 1) % p, inv[i] = _inv[i] * _pow[i - 1] % p;