数学

Solution 1：容易在 $O(n + \log p)$ 时间复杂度内求出 $n$ 个数模 $p$ 意义下的乘法逆元，其中 $p$ 为质数。

令这 $n$ 个数为 $a_1 \sim a_n$，令 $mul_i = \prod\limits_{j=1}^{i} a_j$，快速幂求出 $mul_n^{-1}$ 的值后递推 $mul_{n-1}^{-1} \sim mul_1^{-1}$ 的值。最后 $a_i^{-1} = mul_{i-1} \times mul_{i}^{-1}$，整个过程需要令 $mul_0 = 1$ 避免讨论边界。

Solution 2：更弱但更简洁的做法，只能求 $1 \sim n$ 中每个数模 $p$ 意义下的乘法逆元，时间复杂度 $O(n)$ 与模数无关。

首先有 $1^{-1} \equiv 1 \ (\bmod \ p)$。对于大于 $1$ 的整数 $i$，利用 $i$ 将 $p$ 分解为 $ki + r = p$ 的形式，也就是 $ki + r \equiv 0 \ (\bmod \ p)$，其中 $r < i$。

式子两边同乘 $i^{-1} r^{-1}$ 得到 $kr^{-1} + i^{-1} \equiv 0 \ (\bmod \ p)$，于是 $i^{-1} \equiv -kr^{-1} \equiv - \left\lfloor \dfrac{p}{i} \right\rfloor (p \bmod i)^{-1} \ (\bmod \ p)$，递推即可。