题目链接

知识点分析：

1. 快速幂
2. 前缀和思想（实际上叫前缀积）
3. 快速幂求逆元

题目大意：

给定一个长度大小为{N}的正整数数组，查询{M}轮，每次问一个区间所有元素的连续乘积。
由于这个答案可能很大，你只用输出结果对{10^9+7}取余数后的结果即可。

问题分析：

观察问题要求一个区间所有元素的连续乘积，则可以考虑用前缀和思想，用一个s数组来存前缀积。

比如s[i]就表示前i个元素的乘积。

我们知道前缀和公式：

s[0] = 0;//初始化
for(int i = 1;i<=n;i++)
    s[i] = s[i-1]+a[i]

则不难得出前缀积为：

s[0] = 1;//初始化
for(int i = 1;i<=n;i++)
    s[i] = s[i-1]*a[i];

而观察数据量最大到1e5,而每个数字最大是1e9，假设数据均取最大值，那么s[n] = (1e5)^(1e9)。
（应注意不是1e14，而是1e5个1e9相乘，不是相加）
所以注意前缀积计算时应该%1e9+7(1e9+7是题目给出的值

s[0] = 1;//初始化
for(int i = 1;i<=n;i++)
    s[i] = (s[i-1]*a[i])%mod;

到这里前缀积算是预处理完了，最开始我想的是直接类似求区间和的操作s[y]-s[x-1]，
那么求区间乘积就应该是s[y]/s[x-1]；

于是交了一次又一次WA代码：

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N = 1e5+10;

ll mod = 1e9+7;
ll a[N];
ll b[N];
int n,m;
int main()
{
    cin>>n>>m;
    a[0] = 1;
    b[0] = a[0];
    for(int i = 1;i<=n;i++)
    {
        cin>>a[i];
        b[i] = (b[i-1]*a[i])%mod;
    }
    while(m--)
    {
        int x,y;
        cin>>x>>y;
        cout<<(b[y]/b[x-1])%mod<<endl;
    }
    return 0;
}

于是在询问了群里各位大佬以后，才明白：在取模意义下是不能直接通过除号来做除法操作的。


例如：对5取余时， 7/3 = 2/3 ,虽然在前缀积处理上直观感觉没问题，但是实际上计算模意义下的前缀积时，已经不满足直接b[y]/b[x-1]求前缀乘积的性质了。

所以模意义下要做除法应当引入逆元 这个概念：

粗略的定义就是：
b[y]/b[x-1] = b[y]*(b[x-1]的乘法逆元)

而逆元可以通过快速幂 来求。

附上一个快速幂板子：

ll qmi(ll a,ll b,ll p)
{
    ll ans = 1;
    while(b)
    {
        if(b&1)
            ans = ans*a%p;
        a = a*a%p;
        b>>=1;
    }
    return ans;
}
//求逆元：
//niyuan = qmi(num,mod-2,mod);

所以AC代码：

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N = 1e5+10;

ll mod = 1e9+7;
ll a[N];
ll b[N];
ll qmi(ll a,ll b,ll p)
{
    ll ans = 1;
    while(b)
    {
        if(b&1)
            ans = ans*a%p;
        a = a*a%p;
        b>>=1;
    }
    return ans;
}
int n,m;
int main()
{
    cin>>n>>m;
    b[0] = 1;
    for(int i = 1;i<=n;i++)
    {
        cin>>a[i];
        b[i] = (b[i-1]*a[i])%mod;
    }
    while(m--)
    {
        int x,y;
        cin>>x>>y;
        cout<<(b[y]*qmi(b[x-1],mod-2,mod))%mod<<endl;
    }
    return 0;
}