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

mrsrz · 2019-06-02 11:23:51 · 题解

不明白其他题解为啥思路那么复杂。只要不被标题骗，这就是一道小学数学题？

这题就是很多个分数加起来。

那么根据小学数学知识，我们只要把所有分数通分就好了。

令s=\prod a_i，那么第i个分数通分后变为\frac{k^i\times(s/a_i)}{s}。

其中s/a_i相当于前面的数的乘积乘上后面的数的乘积，这个O(n)预处理出前、后缀积，然后O(1)求出来。

我们把分子加起来，最后再除以s即可，只需要一次求逆。

时间复杂度O(n)。

Code：

#include<cstdio>
#include<cctype>
typedef long long LL;
int n,k,md,pre[5000005],suf[5000005],a[5000005];
char buf[(int)1e8],*ss=buf;
inline int init(){buf[fread(buf,1,(int)1e8-1,stdin)]='\n';fclose(stdin);return 0;}
const int __START__=init();
inline int readint(){
    int d=0;
    while(!isdigit(*ss))++ss;
    while(isdigit(*ss))d=d*10+(*ss++^'0');
    return d;
}
inline int Inv(const int p){
    if(p==1)return 1;
    return((LL)(md-md/p)*Inv(md%p)%md);
}
int main(){
    n=readint(),md=readint(),k=readint();
    int ans=0;
    for(register int i=*pre=suf[n+1]=1;i<=n;++i)
    pre[i]=(LL)pre[i-1]*(a[i]=readint())%md;
    for(register int i=n;i;--i)
    suf[i]=(LL)suf[i+1]*a[i]%md;
    for(register int i=1,j=k;i<=n;++i,j=(LL)j*k%md)
    ans=(ans+(LL)j*pre[i-1]%md*suf[i+1])%md;
    printf("%lld",ans*(LL)Inv(pre[n])%md);
    return 0;
}