题解 | 子数列求积

就是做一个前缀积，pre[i]是前i项累乘。与前缀和类似，求出[l,r]区间的乘积可以表示为pre[r]/pre[l-1]，但是注意到这题有取模操作，所以除一个数需要转化为乘法逆元，所以查询结果就是pre[r]*inv(pre[l-1])。没见过乘法逆元的可以了解一下费马小定理等知识点。

乘法逆元的计算是利用快速幂qpow的，快速幂可以将求x的n次方问题复杂度降到O（logn），这又是一个基础内容了。

using namespace std;
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define PII pair<int,int>
#define PLL pair<ll,ll>
const ll mod=1e9+7;
ll qpow(ll a,ll b)
{
    ll ans=1;
    while(b)
    {
        if(b%2==1)
        {
            ans=ans*a%mod;
        }
        b/=2;
        a=a*a%mod;
    }
    return ans;
}
void solve(){
    int n,q;
    cin>>n>>q;
    vector<ll>pre(n+1,1);
    for(int i=1;i<=n;i++)cin>>pre[i];
    for(int i=1;i<=n;i++)pre[i]*=pre[i-1],pre[i]%=mod;
    while(q--){
        int l,r;
        cin>>l>>r;
        ll ans=pre[r]*qpow(pre[l-1],mod-2)%mod;
        cout<<ans<<' ';
    }
}
int main(){
	int T=1;
	// cin>>T;
	while(T--)
	solve();
}