题目链接：https://www.luogu.com.cn/problem/P5431。

题外话

其实我觉得这道题的考点是快读.jpg

没有快读的后果

正文

以下运算均在模 $p$ 意义下进行。

$$ \sum_{i=1}^{n}{\frac{k^i}{a_i}}=\sum_{i=1}^{n}{k^i\cdot a_i^{-1}} $$

我们考虑先求出 $a$ 序列的前缀积，记为 $s$：

$$ s_i=\prod_{j=1}^{i}{a_j} $$

记 $a$ 序列前缀积的逆元为 $t$，此时如果我们知道这个序列，我们就可以知道 $a$ 中任意一个数的逆元：

$$ a_i^{-1}=s_{i-1}\cdot t_i $$

而「前缀积的逆元」就等于「逆元的前缀积」，所以我们只要求出 $t_n$ 就可以线性递推出整个 $t$ 序列了：

$$ t_n=s_n^{p-2} $$

$$ t_i=a_{i+1}\cdot t_{i+1} $$

这样我们就求得了 $a$ 序列的逆元，再用秦九韶算法就能在线性时间内算出题目的式子了。

参考代码

前方极差码风警告！

#include <cstdio>

#define N 5000010
#define re register
#define gc pa==pb&&(pb=(pa=buf)+fread(buf,1,100000,stdin),pa==pb)?EOF:*pa++
typedef long long ll;
static char buf[100000],*pa(buf),*pb(buf);
inline int read() {
    re int x(0);re char c(gc);
    while(c<'0'||c>'9')c=gc;
    while(c>='0'&&c<='9')
        x=x*10+c-48,c=gc;
    return x;
}

inline int pow(int a,int b,int p) {
    int ans(1);
    while(b)
        ans=b&1?(ll)ans*a%p:ans,a=(ll)a*a%p,b>>=1;
    return ans;
}

int n,p,k,a[N],s[N]={1},inv_s[N],ans;

int main() {
    n=read(),p=read(),k=read();
    for(int i=1;i<=n;++i)
        a[i]=read(),s[i]=(ll)s[i-1]*a[i]%p;
    inv_s[n]=pow(s[n],p-2,p);
    for(int i=n-1;i;--i)
        inv_s[i]=(ll)inv_s[i+1]*a[i+1]%p;
    for(int i=n;i;--i)
        ans=((ll)inv_s[i]*s[i-1]%p+ans)*k%p;
    printf("%d",ans);
    return 0;
}

评测记录

$5\times10^6$ 的输入，千万记得快读！