洛谷 P5431 【模板】乘法逆元2（卡常）

传送门

---

解题思路

在 (O(n)) 内求出 (n) 个数的逆元：
令 (S=sum_{i=1}^{n}a[i])，
则 (a[i]^{-1}=frac{S/a[i]}{S}=S_1[i-1]*S_2[n-i]*S^{-1})。
其中 (S_1) 为 (a[i]) 的前缀积，(S_2) 为 (a[i]) 的后缀积。
(O(n)) 预处理，(O(1)) 求。
因为这次要卡常，所以用了题解的快读（真的强大）

AC代码

#include<cstdio>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn=5e6+5;
int n,p,k,k0,s1[maxn],s2[maxn],a[maxn];
long long ans;
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;
        c=getchar();
    }
    x*=fu;
}
int ksm(int a,int b){
	if(b==1) return a%p;
	long long res=ksm(a,b/2);
	if(b&1) return (long long)res*res%p*a%p;
	return	(long long)res*res%p;
}
int main(){
	read(n);
	read(p);
	read(k0);
	k=k0;
	s1[0]=s2[0]=1;
	for(int i=1;i<=n;i++){
		read(a[i]);
		s1[i]=(long long)s1[i-1]*a[i]%p;
	}
	for(int i=1;i<=n;i++){
		s2[i]=(long long)s2[i-1]*a[n-i+1]%p;
	}
	for(int i=1;i<=n;i++){
		ans+=(long long)k*s1[i-1]%p*s2[n-i]%p;
		k=(long long)k*k0%p;
	}
	printf("%lld",ans%p*ksm(s1[n],p-2)%p);
    return 0;
}