正题

题目链接:

题目大意

一个长度为 $n$ 的序列 $a$ 。

求 $(\sum_{i=1}^n \frac{k^i}{a_i})\% p$

解题思路

定义 $s_i=\prod_{i=1}^ia_i$

\frac{1}{s_{i-1}}=\frac{1}{s_{i}}*a_i

\frac{1}{a_i}=\frac{1}{s_i}*s_{i-1}

然后我们可以

O (n)

推出

s_n

，然后求出

\frac{1}{s_n}

。然后倒推回去求出所有的

s_i

。

$c o d e$

#pragma GCC optimize(2)%:pragma GCC optimize(3)%:pragma GCC optimize("Ofast")%:pragma GCC optimize("inline")%:pragma GCC optimize("-fgcse")%:pragma GCC optimize("-fgcse-lm")%:pragma GCC optimize("-fipa-sra")%:pragma GCC optimize("-ftree-pre")%:pragma GCC optimize("-ftree-vrp")%:pragma GCC optimize("-fpeephole2")%:pragma GCC optimize("-ffast-math")%:pragma GCC optimize("-fsched-spec")%:pragma GCC optimize("unroll-loops")%:pragma GCC optimize("-falign-jumps")%:pragma GCC optimize("-falign-loops")%:pragma GCC optimize("-falign-labels")%:pragma GCC optimize("-fdevirtualize")%:pragma GCC optimize("-fcaller-saves")%:pragma GCC optimize("-fcrossjumping")%:pragma GCC optimize("-fthread-jumps")%:pragma GCC optimize("-funroll-loops")%:pragma GCC optimize("-fwhole-program")%:pragma GCC optimize("-freorder-blocks")%:pragma GCC optimize("-fschedule-insns")%:pragma GCC optimize("inline-functions")%:pragma GCC optimize("-ftree-tail-merge")%:pragma GCC optimize("-fschedule-insns2")%:pragma GCC optimize("-fstrict-aliasing")%:pragma GCC optimize("-fstrict-overflow")%:pragma GCC optimize("-falign-functions")%:pragma GCC optimize("-fcse-skip-blocks")%:pragma GCC optimize("-fcse-follow-jumps")%:pragma GCC optimize("-fsched-interblock")%:pragma GCC optimize("-fpartial-inlining")%:pragma GCC optimize("no-stack-protector")%:pragma GCC optimize("-freorder-functions")%:pragma GCC optimize("-findirect-inlining")%:pragma GCC optimize("-fhoist-adjacent-loads")%:pragma GCC optimize("-frerun-cse-after-loop")%:pragma GCC optimize("inline-small-functions")%:pragma GCC optimize("-finline-small-functions")%:pragma GCC optimize("-ftree-switch-conversion")%:pragma GCC optimize("-foptimize-sibling-calls")%:pragma GCC optimize("-fexpensive-optimizations")%:pragma GCC optimize("-funsafe-loop-optimizations")%:pragma GCC optimize("inline-functions-called-once")%:pragma GCC optimize("-fdelete-null-pointer-checks")#include
   
    #include
    
     #include
     
      #include
      
       #define ll long longusing namespace std;const ll N=5e6+10;ll n,p,K,S,a[N],s[N],k[N],ans; __attribute__((optimize("O3"))) inline int read() {
   	int x=0,f=1; char c=getchar();	while(!isdigit(c)) {
   if(c=='-')f=-f;c=getchar();}	while(isdigit(c)) x=(x<<1)+(x<<3)+c-48,c=getchar();	return x*f;}ll power(ll x,ll b,ll p){
   	ll ans=1;	while(b){
   		if(b&1) ans=ans*x%p;		x=x*x%p;b>>=1;	}	return ans;}int main(){
   	n=read();p=read();K=read();	S=1;k[0]=1;s[0]=1;	for(int i=1;i<=n;i++){
   		a[i]=read();		S=S*a[i]%p;s[i]=S;		k[i]=k[i-1]*K%p;	}	S=power(S,p-2,p);	for(int i=n;i>=1;i--)	{
   		ll inv=S*s[i-1]%p;		S=S*a[i]%p;		(ans+=k[i]*inv%p)%=p;	}	printf("%lld",ans);}