这个是题解第二篇的代码的主函数部分

	b[n + 1] = 1;
    s[0] = 1;
    for (register int i = 1;i <= n;i ++)//线性求si
    {
        read(a[i]);
        s[i] = (s[i - 1] * a[i]) % MOD;
        //cout<<s[i]<<" ";
    }
    b[n + 1] = ksm(s[n], MOD - 2);//求逆元
    //cout<<b[n+1]<<endl;
    for (register int i = n;i >= 1;i --)//线性求1/si
    {
        b[i] = (b[i + 1] * a[i]) % MOD;
    }
    LL tmp = k;
    for (register int i = 1;i <= n;i ++)//线性求答案
    {
        ans = (ans + ((b[i + 1] * s[i - 1]) % MOD) * tmp) % MOD;
        tmp = (tmp * k) % MOD;
        //cout<<ans<<" "<<tmp<<endl;
    }

然后我跟着他的式子滤了一遍之后，发现该部分和他求的式子不是很相同，可能有一些地方用了优化

然后我根据他得思路打了一遍后，感觉时间复杂度挺低得了，还是不过

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<stack>
#include<algorithm>
#define int long long 
using namespace std;
const int maxn=5e6+9;
int n,mod,k,ans;
int s[maxn],inv[maxn],a[maxn];//inv为s数组的逆元，s数组为前缀积 
template <typename T>//自动定义类型，快读不理解只能这样=_=
inline void read(T &x)
{
	char c;
	x=0;
	int fu=1;
	c=getchar();
	while(c>57||c<48)
	{
		if(c==45)fu=-1;
		c=getchar();
	}
	while(c<=57&&c>=48)
	{
		x=(x<<3)+(x<<1)+c-48;//相当于x*=10，二进制运算快
		c=getchar(); 
	}
	x*=fu;
} 
int necy(int x,int y)//快速幂求逆元 
{
	int ret=1;
	int tem=y;
	while(tem>0)
	{
		if(tem&1)ret=(ret*x)%mod;
		tem>>=1;
		x=(x*x)%mod;
		
	}
	ret%=mod;
	return ret;
}
signed main()
{
	read(n);
	read(mod);
	read(k);
	s[0]=1;//初始化；
	inv[n+1]=1; 
	for(int i=1;i<=n;++i)
	{
		read(a[i]);
		s[i]=(s[i-1]*a[i])%mod;//s数组中存前缀积 
		//cout<<s[i]<<" ";
	}
	inv[n]=necy(s[n],mod-2);//s[n]的逆元 
	//cout<<inv[n+1]<<endl;
	for(int i=n-1;i>=1;--i)
	{
		inv[i]=(inv[i+1]*a[i+1])%mod;
	}
	int tmp=k;
	for(int i=1;i<=n;++i)
	{
	    int iv = (inv[i] * s[i - 1]) % mod;//这个东西是你求得逆元，tmp一开始是k，也就是k^1，也就是题目中给出的。 
		ans=(ans+(iv*tmp)%mod)%mod;//而且 tmp 每次都乘以 k， 也就是次数加一。 
		tmp=(tmp*k)%mod;
		//cout<<ans<<" "<<tmp<<endl;
	}
	printf("%lld",ans);
	return 0;
}