题解 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的逆元。

具体可见代码：

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;
}

}