线性递推逆元

其实这个并没有什么卵用，基本没有人会卡。

对于求单个数的逆元我们有 \(O(\log n)\) 的算法，因此，如果我们要求 \([1, n]\) 的所有数的逆元的话，朴素的做法是可以做到 \(O(n\log n)\) 的，但是其实我们有线性递推的算法，假设我们要求 \(i\) 在模 \(P\) 意义下的逆元，且 \([1, i - 1]\) 的逆元已经求出：

设 \(P = ki + r\)，其中 \(k = \left\lfloor \frac{P}{i} \right\rfloor, r = P \bmod i < i\)，我们有： \[ ki + r \equiv 0 \pmod{P} \] 两边同时乘上 \(i^{-1}r^{-1}\)： \[ \begin{aligned} kr^{-1} + i^{-1} &\equiv 0 &\pmod{P} \\ i^{-1} &\equiv -kr^{-1} &\pmod{P} \\ i^{-1} &\equiv -\left\lfloor\frac{P}{i}\right\rfloor (P \bmod i)^{-1} &\pmod{P} \end{aligned} \] 由于我们之前已经求得了 \(P \bmod i\) 的逆元，\(i\) 的逆元依上式可以直接递推，代码也很短：

inv[1] = 1;
for (int i = 2; i <= n; i++)
    inv[i] = (-(P / i) * inv[P % i] % P + P) % P;

但是真的没有卵用啊，\(P\) 动不动就是 \(998244353\) 或者 \(1 \times 10^9 + 7\) 这种，就算你能线性递推时间和空间也要炸糊的。