题解 p5431 [模板]乘法逆元2

using namespace std;
int n, a[5000010], inv[5000010], pw[5000010], k, p;
char buf[64000000], *st = buf, *en = buf;
inline int () {
    if(st == en) st = buf, en = buf + fread(buf, 1, 64000000, stdin);
    return *(st++);
}
inline int read() {
    int a = 0, c;
    for(c = gc(); c < '0' || c > '9'; c = gc());
    for(; c >= '0' && c <= '9'; c = gc()) a = (a << 1) + (a << 3) + (c ^ 48);
    return a;
}
inline int power(int a, int b) {
    long long res = a, ans = 1;
    for(; b; b >>= 1, res = res * res % p) if(b & 1) ans = ans * res % p;
    return ans;
}
int main() {
    n =read(), p = read(), k = read();
    k %= p;
    for(register int i = 1; i <= n; i++) a[i] = read();
    pw[0] = a[0] = 1;
    for(register int i = 1; i <= n; i++) pw[i] = 1ll * a[i] * pw[i - 1] % p;
    inv[n] = power(pw[n], p - 2);
    int ans = 0, nowk = 1;
    for(register int i = n; i > 0; i--) inv[i - 1] = 1ll * inv[i] * a[i] % p;
    for(register int i = 1; i <= n; i++) {
        nowk = 1ll * nowk * k % p;
        ans = (ans + 1ll * nowk * inv[i] % p * pw[i - 1]) % p;
    }
    return cout << ans << endl, 0;
}