题解 | #子数列求积#

本题是经典前缀积问题。

核心思路

核心观察

定义前缀积数组 pref：

• pref[0] = 1
• pref[i] = (a_1 \times a_2 \times \cdots \times a_i) \mod M

则区间乘积可表示为：

但 模运算中不能直接做除法！

算法步骤

1. 前缀积表示正确
   在整数域恒成立。

2. 模逆元合法

   • 是质数；
   • 题目保证 ，故 ；
   • 因此 ，逆元存在且唯一；
   • 费马小定理适用， 成立。

3. 边界情况覆盖

   • ：，逆元为 1，结果为 ，正确；
   • ：结果为 ，公式仍成立。

4. 无溢出风险

   • 使用 long long（64 位），最大中间值 ，安全。

5. 输出格式正确

   • " \n"[j == q - 1] 确保空格分隔、末尾换行，符合要求。

复杂度分析

• 时间复杂度：
  单次查询 快速幂约 30 次操作 总查询 ，实际为
• 空间复杂度：
  存储前缀积数组

数学逻辑推导

模逆元（Modular Inverse）的求解

对于整数 和质数模数 ，若 （即 ），
则存在唯一整数 ，求解方法为：

为 在模 意义下的乘法逆元。

数学原理：模逆元（Modular Inverse）

在模 （质数）下，若 ，则存在唯一整数 使得：

于是：

费马小定理求逆元

由于 是质数，根据 费马小定理：

因此：

题目保证 且 ，所以所有 pref[i] ≠ 0，逆元一定存在！

快速幂优化

计算 使用 快速幂（Exponentiation by Squaring），时间复杂度 次操作。

代码

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

const long long MOD = 1000000007LL;

// 快速幂
long long qpow(long long a, long long b, long long c = MOD) {
    a %= c;
    long long ans = 1;
    while (b) {
        if (b & 1) 
            ans = (ans * a) % c;
        a = (a * a) % c;
        b >>= 1;
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);

    int n, q;
    cin >> n >> q;
    vector<long long> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    vector<long long> pref(n + 1, 1);//前缀积
    for (int i = 0; i < n; i++) {
        pref[i + 1] = pref[i] * a[i] % MOD;
    }

    for (int j = 0; j < q; j++) {
        int l, r;
        cin >> l >> r;
        long long prod = pref[r] * qpow(pref[l - 1], MOD - 2) % MOD;
        cout << prod << " \n"[j == q - 1];//小技巧昂"\n"[0]意思是空格，1就是换行
    }

    return 0;
}