[luogu_p5431] [template] multiplicative inverse 2 [number theory]

Ideas ：

Obviously, let's ask ai Inverse element
Then just push ：
We set up si by ai Prefix product of
So easy to get ：
$$\frac{1}{s_{i-1}}=\frac{1}{s_i}\times a_i$$
namely
$$\frac{1}{a_i}=\frac{s_{i-1}}{s_i}$$
First of all sn The inverse of is solved by Fermat's theorem , And then linearly recurs back s Array , namely ：
$$\frac{1}{s_{i-1}}=\frac{1}{s_i}\times a_i$$
hold s After finding the inverse of , You can recurse linearly a The inverse of

$code$

#include<iostream>
#include<cstdio>
#define ll long long
#define re register

using namespace std;

const ll MAXN = 5e6 + 10;

ll n, p, k;
ll s[MAXN], b[MAXN], a[MAXN];


inline int read() {
    
   ll s=0, w=1;
   char ch = getchar();
   while(ch < '0' || ch > '9') {
     if(ch == '-') w = -1; ch = getchar(); }
   while(ch >= '0' && ch <= '9') s = s * 10 + ch - '0', ch = getchar();
   return s * w;
}

inline ll qpow(ll x, ll k) {
    
	re ll ans = 1;
	while(k) {
    
		if(k & 1) ans = ans * x % p;
		x = x * x % p;
		k >>= 1;
	}
	return ans;
}

int main() {
    
	n = read(), p = read(), k = read();
	s[0] = 1;
	for(re ll i = 1; i <= n; ++ i) {
    
		a[i] = read();
		s[i] = s[i - 1] * a[i] % p;
	}
	b[n + 1] = qpow(s[n], p - 2);
	for(re ll i = n; i >= 1; -- i)
		b[i] = b[i + 1] * a[i] % p;
	re ll q = 1, ans = 0;
	for(re ll i = 1; i <= n; ++ i)
		q = q * k % p, ans = (ans + q * s[i - 1] % p * b[i + 1]) % p;
	printf("%lld", ans);
	return 0;
}