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

发表于 | 分类于 | 阅读次数：

题面

给定$n$个数，$O(n)$求所有数的逆元
考虑类似求组合数时预处理阶乘逆元的方法
求出前缀累乘
然后再倒着求出前缀累乘的逆元
注意读入优化 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <bits/stdc++.h>
using namespace std;
int n, a[5000010], inv[5000010], pw[5000010], k, p;
char buf[64000000], *st = buf, *en = buf;
inline int gc() {
    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;
}