不明白其他题解为啥思路那么复杂。只要不被标题骗,这就是一道小学数学题?
这题就是很多个分数加起来。
那么根据小学数学知识,我们只要把所有分数通分就好了。
令$s=\prod a_i$,那么第$i$个分数通分后变为$\frac{k^i\times(s/a_i)}{s}$。
其中$s/a_i$相当于前面的数的乘积乘上后面的数的乘积,这个$O(n)$预处理出前、后缀积,然后$O(1)$求出来。
我们把分子加起来,最后再除以$s$即可,只需要一次求逆。
时间复杂度$O(n)$。
## Code:
```cpp
#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;
}
```