枫林晚 的博客

枫林晚 的博客

题解 P5431 【【模板】乘法逆元2】

posted on 2019-05-31 19:53:12 | under 题解 |

就是一个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;
}

}