一、？？？
1. 线性求逆元
我们记原数为 \(x\)，模数为 \(p\)
那我们有 \(a,b\in\mathbb{Z}(x>b)\)
\[p = ax + b \]那么：
\[ax+b\equiv0\mod p \]两边同乘 \(x^{-1}\times b^{-1}\)：
\[a\times b^{-1}+k^{-1} \equiv 0\mod p \]\[\Downarrow \]\[k^{-1}\equiv-a\times b^{-1}\mod p \]又因为：
\[a = \lfloor\frac p x\rfloor\\b = p\bmod x \]那么：
\[k^{-1} \equiv -\lfloor\frac p x\rfloor\times (p\bmod x)^{-1} \mod p \]inv[1] = 1;
for(int i = 2;i <= n;i++)
inv[i] = ((p - p / i) * inv[p % i] % p + p) % p;
2. 前缀积法求逆元
给定任意一些数 \(a_1,a_2,\cdots,a_n\)，求 \({a_1}^{-1},{a_2}^{-1},\cdots,{a_n}^{-1}\)
你考虑，记 \(pre_i = \prod\limits_{i=1}^n a_i~,invp_i = \prod\limits_{i=1}^n ({a_i}^{-1}),inva_i = {a_i}^{-1}\)
对于 \(pre_i\) 显然是个前缀积即可：\(pre_i = pre_{i-1}\times a_i\)
对于 \(invp_i\)，先求出 \(invp_n\) （跑一遍逆元），再 \(invp_i = invp_{i+1}\times a_{i+1}\)
对于 \(inva_i\)，就是 \(inva_i~ = invp_{i} \times pre_{i-1}\) （\({\prod_{j=1}^i a_{j}^{-1}} \times \prod_{j=1}^{i-1} a_{j}\) ）
typedef long long ll;
ll pre[NN],invp[NN],a[NN],inva[NN];
ll inv(ll x){...}//求逆元函数
void init(){
pre[0] = 1;
for(int i = 1; i <= n; ++i) pre[i] = pre[i-1] * a[i] % MOD;
invp[n] = inv(pre[n]);
for(int i = n - 1; i >= 1; --i) invp[i] = invp[i+1] * a[i + 1] % MOD;
for(int i = 1; i <= n; ++i) inva[i] = invp[i] * pre[i - 1];
}