正常求逆元
由费马小定理
\[a^p\equiv a\pmod{p} \quad p\in prime
\]
得：
\[a^{p-2}\equiv \dfrac{1}{a}\pmod{p}
\]
之后称 \(a\) 关于模 \(p\) 的乘法逆元为 \(inv(a)\)
求 \(inv(a)\) 的时间复杂度为 \(O(\log p)\) （快速幂）
线性求 \(inv(i) \ (1\leqslant i\leqslant n)\)
即要 \(O(1)\) 在已知 \(inv(j) \ (1\leqslant j\leqslant i-1)\) 的前提下求 \(inv(i)\)
推导：
将 \(p\) 拆开
\[p=\left\lfloor\dfrac{p}{i}\right\rfloor\times i+p\%i
\]
得
\[\left\lfloor\dfrac{p}{i}\right\rfloor\times i+p\%i\equiv 0\pmod{p}
\]
两边同乘 \(inv(i)\times inv(p\%i)\)，得
\[\left\lfloor\dfrac{p}{i}\right\rfloor\times inv(p\%i)+inv(i)\equiv 0\pmod{p}
\]
即
\[inv(i)\equiv -\left\lfloor\dfrac{p}{i}\right\rfloor\times inv(p\%i)\pmod{p}
\]
其中 \(inv(p\%i)\) 我们已知，就能线性求 \(inv(i) \ (1\leqslant i\leqslant n)\) 啦~
线性求 \(inv(i!) \ (1\leqslant i\leqslant n)\)
先求出 \(inv(n!)\)，之后
\[inv(i!)=inv((i+1)!)\times (i+1) \ (1\leqslant i\leqslant n-1)
\]
就结束了~
当然这个也可以配合 \(i! \ (0\leqslant i\leqslant n-1)\) 导出 \(inv(i) \ (1\leqslant i\leqslant n)\) 的取值，也就是
\[inv(i)=inv(i!)\times (i-1)! \ (1\leqslant i\leqslant n)
\]