题意描述

  • nn个元素，mm次询问，输出区间乘积对 10000000071000000007 取模的结果。

制约

1≤n,m≤105,1≤ai≤1091 \le n, m\le 10^5,1\le a_i\le 10^9

解答

∏i=lrai=∏i=1rai∏i=1l−1ai\displaystyle\prod_{i = l}^{r}a_i = \dfrac{\displaystyle\prod_{i=1}^{r}a_i}{\displaystyle\prod_{i=1}^{l-1}a_i}

  • 记录一个「前缀积」，a0a_0 初始化为 11

  • 问题的关键在于对 1e9+71e9+7 取模，在处理前缀积的时候可 (a×b)%mod(a\times b)\% mod，但在回答的时候则需要使用 %mod\%mod 意义下的的乘法逆元，由于 1e9+71e9+7 是一个素数，由 费马小定理，此时的逆元可以直接使用快速幂来求。

参考代码

#include <bits/stdc++.h>
#define forn(i, s, e) for (int i = s; i <= int(e); ++i)
#define forr(i, e, s) for (int i = e; i >= int(s); --i)
#define ii(t) scanf("%d", &t)
#define ii2(a, b) scanf("%d%d", &a, &b)

using namespace std;
using ll = long long;
static const int mod = 1000000007; // 998244353;
static const int N = 7 + 100000;

ll a[N];
ll qmi(ll n, ll m) {
    ll ans = 1 % mod;
    for (; m; m >>= 1) {
        if (m & 1) ans = ll(ans) * n % mod;
        n = ll(n) * n % mod;
    }
    return ans;
}
int main() {
    int n, m, l, r, t; ii2(n, m);
    a[0] = 1;
    forn(i,1,n) ii(t), a[i] = (a[i - 1] * t) % mod;
    while (m --) {
        ii2(l, r);
        printf("%d\n", a[r] % mod * qmi(a[l - 1], mod - 2) % mod);
    }
    return 0;
}