自动搬运

查看原文

来自洛谷，原作者为

	zzy0618 VK100.01 P

搬运于2025-08-24 22:10:40，当前版本为作者最后更新于2025-08-12 15:13:36，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

前置知识：$O(\log P)$ 的方式求单个数的逆元。

题目让我们 $O(n)$ 求 $n$ 的数的逆元。

设 $S=\prod_{i=1}^n a_i$，我们可以轻松求出模意义下 $S^{-1}$ 也就是 $\frac{1}{\prod_{i=1}^n a_i}$。

我们再求一个前缀积 $p_i=\prod_{j=1}^i a_j$，后缀积 $q_i=\prod_{j=i}^n a_j$。

这是，我们发现 $a_i^{-1}=\frac{1}{a_i}=\frac{(\prod_{j=1}^{i-1} a_j)\times (\prod_{j=i+1}^n a_j)}{\prod_{i=1}^n a_i}=p_{i-1}q_{i+1}S^{-1}$。

$S^{-1},p,q$ 都是事先求好的，于是我们得到了 $O(n+\log P)$ 的做法。

#include<bits/stdc++.h>
using namespace std;
char buf[1<<21],*p1=buf,*p2=buf;
int getc(){
	return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;
}void read(int &x) {
    x=0;char ch=getc();
    while(ch<'0'||ch>'9')ch=getc();
    while(ch>='0'&&ch<='9')x=x*10+ch-48,ch=getc();
}const int N=5000005;
int n,P,k,inv,ans;
int p[N],q[N],a[N];
inline int qp(int x,int y){
	int res=1;
	for(;y;y>>=1,x=1ll*x*x%P)
		if(y&1)res=1ll*x*res%P;
	return res;
}signed main(){
	read(n);read(P);read(k);
	p[0]=q[n+1]=1;
	for(int i=1;i<=n;++i)
		read(a[i]);
	for(int i=1;i<=n;++i)
		p[i]=1ll*p[i-1]*a[i]%P;
	for(int i=n;i>=1;--i)
		q[i]=1ll*q[i+1]*a[i]%P;
	inv=qp(p[n],P-2);
	for(int i=1,s=k;i<=n;++i)
		ans=(ans+1ll*s*inv%P*p[i-1]%P*q[i+1]%P)%P,
		s=1ll*s*k%P;
	cout<<ans<<'\n';
	return 0;
}