每日归档： 2019年11月15日

挺套路的。
先计算出所有数的积的逆元，再计算除了这个数以外的数的积，然后乘一起，这样就完成了线性求逆元。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;

typedef long long ll;
const int N=5000005;
inline int rd(){
	int rt=0;char ch=getchar();
	while(!isdigit(ch)){ch=getchar();}
	while(isdigit(ch)){rt=rt*10+ch-'0';ch=getchar();}
	return rt;
}
int n,MOD,k;
int a[N],pr[N],sf[N];
inline int pw(int A,int X){
	int RT=1;
	while(X){
		if(X&1){
			RT=1ll*RT*A%MOD;
		}
		A=1ll*A*A%MOD;X>>=1;
	}
	return RT;
}

void init(){
	scanf("%d%d%d",&n,&MOD,&k);
	int pl=1;
	pr[0]=sf[n+1]=1;
	for(int i=1;i<=n;++i){
		a[i]=rd();
	}
	for(int i=1;i<=n;++i){
		pr[i]=1ll*pr[i-1]*a[i]%MOD;
	}
	pl=pw(pr[n],MOD-2);
	for(int i=n;i>=1;--i){
		sf[i]=1ll*sf[i+1]*a[i]%MOD;
	}
	int nk=1;
	int ans=0;
	for(int i=1;i<=n;++i){
		nk=1ll*nk*k%MOD;
		ans+=1ll*(1ll*pr[i-1]*sf[i+1]%MOD)*(1ll*pl*nk%MOD)%MOD;ans%=MOD;
	}
	printf("%d\n",ans);
	
}
int main(){
	init();
	return 0;
}