题解 | #子数列求积#

前缀和（积）

板子题。

如果根据 次询问每一次都乘一次，复杂度为 肯定是超时的，那我们进行前缀乘积处理，若输入为 ，我们把数组第 0 位初始化为 1：

那么再使用一个前缀积数组，第 位表示 ：

这样对于每次查询输入的 ，直接输出 就是所求结果

模逆元

由于需要你对结果 取余求出，如果数字特别特别大，则需要边处理边求余，例如针对

那么前缀积数组即:

但是显然不能直接相除，这里就需要一个模逆元来处理：

其中 ，具体证明见 OI-Wiki。

关键是我们如何理解它，我们都知道除法运算本质上就是乘这个数的逆元，在有理数范围内定义乘法函数 ，那么单位元表示的是 ，因为 1 与任何一个数 结果不变。如果若能使 ，那么称 互为逆元，即 ，那么定义在模运算的除法 等价于 ，只需要计算出 的逆元 即可，那么根据费马小定理 然后使用快速幂即可求出在模意义下的逆元，复杂度为 。

AC Code

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
constexpr int p = 1e9 + 7;
i64 binpow(i64 a, i64 b, i64 p)
{
    i64 res = 1;
    while (b > 0)
    {
        if (b & 1)
            res = res * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return res;
}
i64 inv(i64 a, i64 p) { return binpow(a, p - 2, p); }
int main(int argc, char *argv[])
{
    int n, q;
    cin >> n >> q;
    vector<int> vi(n + 1);
    vector<int> prefix_mul(n + 1);
    vi[0] = 1;
    prefix_mul[0] = 1;
    for (int i = 1; i <= n; i++)
    {
        cin >> vi[i];
    }
    i64 mul = 1;
    for (int i = 1; i <= n; i++)
    {
        mul *= vi[i];
        mul %= p;
        prefix_mul[i] = mul;
    }
    for (int i = 0; i < q; i++)
    {
        int x, y;
        cin >> x >> y;
        i64 res = prefix_mul[y] * inv(prefix_mul[x - 1], p);
        res %= p;
        cout << res << " ";
    }

    return 0;
}