看到5e6的数据,500ms的时限，\(O(NlogN)\)快速幂直接跑肯定会T掉，那我们就要考虑优化一下式子。
我们令\(s = \prod_{1}^{n}{a[i]}\) ,那我们给第i个式子通分，就为$ \frac{k^i*s/a[i]}{s} $
\(s/a[i]\) 就相当于$ \prod ^{i-1}_{1}{a[i]}* \prod _{i+1}^{n}{a[i]}$
因此我们只需要预处理出前缀积和后缀积，最后只需要求一遍\(s[n]\)的逆元就可以。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=6e6+107;
int n,p,k,ans;
int a[N],b[N],s[N];
int read()
{
int f=1,s=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){s=(s<<1)+(s<<3)+(ch^48);ch=getchar();}
return f*s;
}
int qpow(int a,int b)
{
int ans=1;
while(b)
{
if(b&1) ans=ans*a%p;
b=b>>1;
a=a*a%p;
}
return ans;
}
signed main()
{
// freopen("in.in","r",stdin);
// freopen("out.out","w",stdout);
n=read(),p=read(),k=read();
s[0]=1;
for(int i=1;i<=n;i++)
{
a[i]=read();
s[i]=s[i-1]*a[i]%p;
}
b[n+1]=1; a[n+1]=1;
for(int i=n;i>=1;i--) b[i]=b[i+1]*a[i+1]%p;
int j=k;
for(int i=1;i<=n;i++,j=j*k%p)
{
ans=(ans+s[i-1]*j%p*b[i]%p)%p;
}
printf("%lld",ans*qpow(s[n],p-2)%p);
}