挺套路的。
先计算出所有数的积的逆元，再计算除了这个数以外的数的积，然后乘一起，这样就完成了线性求逆元。
#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;
}
With havin so much content do you ever run into any issues of plagorism or copyright violation? My blog has
a lot of unique content I’ve either created myself or outsourced but it appears a lot of it is popping it up all
over the internet without my agreement. Do you know any methods to help prevent content from being ripped off?
I’d really appreciate it.
P.S. If you have a minute, would love your feedback on my
new website re-design. You can find it by searching for “royal cbd” – no sweat
if you can’t.
Keep up the good work!
I truly love your website.. Very nice colors & theme.
Did you develop this website yourself? Please reply back as I’m trying to create my very own website and would like to find out where you got this from or just what
the theme is called. Thanks!
P.S. If you have a minute, would love your feedback on my new website
re-design. You can find it by searching for «royal
cbd» — no sweat if you can’t.
Keep up the good work!