快速计算多个树的逆元

设\(n\)个数分别为\(a_1\dots a_n\)，令\(s_i\)为\(a_i\)的前缀积，那么对于\(1\le i<n\)有\(s_i^{-1}=s_{i+1}^{-1}*a_{i+1}\)，那么\(a_i^{-1}=s_i^{-1}*s_{i-1}\)，可以\(\Theta(n+\log p)\)的求出\(n\)个数的逆元
例题：LOJ161乘法逆元 2

#include<cstdio>
typedef long long ll;
const ll mod=1000000007;
inline ll jia(ll x,ll y){
	return x+y<mod?x+y:x+y-mod;
}
inline ll cheng(ll x,ll y){
	return x*y%mod;
}
inline ll pow(ll x,ll y){
	register ll res=1;
	for(;y;x=cheng(x,x),y>>=1)if(y&1)res=cheng(res,x);
	return res;
}
const int N=5000005;
int n;
inline ll read(){
	register ll x=0;
	register char c=getchar();
	for(;c<'0'||c>'9';c=getchar());
	for(;c>='0'&&c<='9';c=getchar())x=(x<<1)+(x<<3)+(c^48);
	return x;
}
ll a[N],ans,sv[N],s[N],p[N];
int main(){
	n=read(),s[0]=p[0]=1;
	for(register int i=1;i<=n;i++)a[i]=read(),s[i]=cheng(s[i-1],a[i]),p[i]=cheng(p[i-1],998244353);
	sv[n]=pow(s[n],mod-2);
	for(register int i=n;i>1;i--)sv[i-1]=cheng(sv[i],a[i]);
	for(register int i=1;i<=n;i++)ans=jia(ans,cheng(cheng(sv[i],s[i-1]),p[n-i]));
	printf("%lld",ans);
	return 0;
}