题目大意
给定 $n$ 个正整数 $\{a_i\}$ 和 $k$，求在模 $p$ 意义下的
$$ \sum_{i=1}^n \frac{k^i}{a_i} \bmod p $$
分析
逐个求逆元是 $O(n \log p)$ 的，肯定会 T，需要想想别的办法。
批量求逆元的一个技巧，先求出 $a_i$ 的前缀积，然后求出全部积的逆元，再逐个往前推。即
$$ (a_n)^{-1} = \left(\prod_{i=1}^{n-1} a_i\right) \left(\prod_{i=1}^n a_i\right)^{-1} $$
显然，$\{a_n\}$ 中不能有 $0$。
vi get_inv(const vi &a, int p) {
int n = a.size() - 1;
vi prod(n + 1);
prod[0] = 1;
for (int i = 1; i <= n; i++) {
prod[i] = 1ll * prod[i - 1] * a[i] % p;
}
prod[n] = qpow(prod[n], p - 2, p);
vi iva(n + 1);
for (int i = n; i >= 1; i--) {
iva[i] = 1ll * prod[i] * prod[i - 1] % p;
prod[i - 1] = 1ll * prod[i] * a[i] % p;
}
return iva;
}