• VIEW

题意描述

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

制约

$1\le n,m\le 10^5,1\le a_i\le 10^{9}1\; \backslash le\; n,\; m\backslash le\; 10^5,1\backslash le\; a\_i\backslash le\; 10^9$

解答

• 记录一个「前缀积」，$a_{0}a\_0$ 初始化为 $11$

• 问题的关键在于对 $1e9+71e9+7$ 取模，在处理前缀积的时候可 $(a\times b)\mathrm{\%}mod(a\backslash times\; b)\backslash \%\; mod$，但在回答的时候则需要使用 $\mathrm{\%}mod\backslash \%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;
}