题目链接：【模板】乘法逆元 2
这道题不建议叫乘法逆元，可以直接当一道数学题去处理，我们观察这个式子 \(\sum\limits_{i=1}^n \frac{k^i}{a_i}\)，那么我们直接通分就和即可，分子就是 \(\sum\limits_{i=1}^nk^i\cdot (a_1\sim a_i-1\cdot a_i+1\sim a_n)\)，预处理出前缀积和后缀积即可，最后乘上 \(1\sim n\) 阶乘的逆元即可。
这道题卡时间，用快读快写可以过。
点击查看代码
#define M 5000010
using namespace std;
int n, p, k, ans, base = 1;
int f[M], g[M], inv[M], a[M];
inline int read() {
int f(1) , x(0);
char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ 48);
return f * x;
}
inline void write(int x) {
if (x < 0) putchar('-'), x = -x;
if (x > 9) write(x / 10);
putchar(x % 10 + '0');
}
int QuickPow(int a, int b) {
int res = 1;
while (b) {
if (b & 1) res = res * a % p;
a = a * a % p;
b >>= 1;
}
return res;
}
int main() {
n = read(), p = read(), k = read();
for (int i = 1; i <= n; i++)
a[i] = read();
g[0] = f[n+1] = 1;
for (int i = 1; i <= n; i++)
g[i] = g[i-1] * a[i] % p;
for (int i = n; i >= 1; i--)
f[i] = f[i+1] * a[i] % p;
for (int i = 1; i <= n; i++) {
base = base * k % p;
ans = (ans + base * g[i-1] % p * f[i+1] % p) % p;
}
int w = QuickPow(g[n], p - 2);
write((ans * w) % p);
return 0;
}