题解 P5431 【【模板】乘法逆元2】
枫林晚
2019-05-31 19:53:12
就是一个trick：$O(n)+log(mod)$离线求逆元
设$s[i]$表示前i个数的连乘积。输入的时候顺便求出
再求出所有的数的乘积的逆元$inv$，即$inv=calcinv(s[n])$
设$iv[i]$表示，前i个数的逆元的连乘积。
发现，对于第i个位置的逆元$ni[i]=iv[i]\times s[i-1]$
而$iv[i]=iv[i+1]\times a[i]$，所以递推即可。
具体实现要卡常：
1.$iv[i]$不用数组，直接在$inv$上做变化即可。
2.为了减少循环次数，倒序计算答案，$k=k^n$，再不断乘上$k$的逆元。
具体可见代码：
```cpp
namespace Miracle{
int mod;
int mul(int x,int y){return (ll)x*y%mod;}
const int N=5e6+3;
int n,k,iv;
int a[N],s[N];
ll ans;
int main(){
rd(n);rd(mod);rd(k);s[0]=1;
for(reg i=1;i<=n;++i){
rd(a[i]);s[i]=mul(s[i-1],a[i]);
}
int inv=qm(s[n]);
iv=qm(k);k=qm(k,n);
for(reg i=n;i>=1;--i){
ans=ad(ans,mul(k,mul(inv,s[i-1])));
inv=mul(inv,a[i]);
k=mul(k,iv);
}
ot(ans);return 0;
}
}
```