题解：P5431 【模板】模意义下的乘法逆元 2
zzy0618
·
·
题解
前置知识：O(\log P) 的方式求单个数的逆元。
题目让我们 O(n) 求 n 的数的逆元。
设 S=\prod_{i=1}^n a_i，我们可以轻松求出模意义下 S^{-1} 也就是 \frac{1}{\prod_{i=1}^n a_i}。
我们再求一个前缀积 p_i=\prod_{j=1}^i a_j，后缀积 q_i=\prod_{j=i}^n a_j。
这是，我们发现 a_i^{-1}=\frac{1}{a_i}=\frac{(\prod_{j=1}^{i-1} a_j)\times (\prod_{j=i+1}^n a_j)}{\prod_{i=1}^n a_i}=p_{i-1}q_{i+1}S^{-1}。
```cpp
#include<bits/stdc++.h>
using namespace std;
char buf[1<<21],*p1=buf,*p2=buf;
int getc(){
return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;
}void read(int &x) {
x=0;char ch=getc();
while(ch<'0'||ch>'9')ch=getc();
while(ch>='0'&&ch<='9')x=x*10+ch-48,ch=getc();
}const int N=5000005;
int n,P,k,inv,ans;
int p[N],q[N],a[N];
inline int qp(int x,int y){
int res=1;
for(;y;y>>=1,x=1ll*x*x%P)
if(y&1)res=1ll*x*res%P;
return res;
}signed main(){
read(n);read(P);read(k);
p[0]=q[n+1]=1;
for(int i=1;i<=n;++i)
read(a[i]);
for(int i=1;i<=n;++i)
p[i]=1ll*p[i-1]*a[i]%P;
for(int i=n;i>=1;--i)
q[i]=1ll*q[i+1]*a[i]%P;
inv=qp(p[n],P-2);
for(int i=1,s=k;i<=n;++i)
ans=(ans+1ll*s*inv%P*p[i-1]%P*q[i+1]%P)%P,
s=1ll*s*k%P;
cout<<ans<<'\n';
return 0;
}
```