题解 | #子数列求积#

题目链接

题目描述

给定一个长度为 $n$ 的正整数序列 $a$ 。接下来有 $q$ 次独立查询，第 $i$ 次查询给出一对下标 $l, r$ ( $1 \le l \le r \le n$ )，请你计算区间乘积 $\prod_{i=l}^{r} a_i$ 并对模数 $10^9+7$ 取模后的结果。

解题思路

本题要求我们高效地计算多次给定区间的乘积。如果对每次查询都遍历区间 $[l, r]$ 进行计算，在查询次数 $q$ 和区间长度都很大的情况下，总时间复杂度会达到 $\mathcal{O}(q \cdot n)$ ，这通常会超出时间限制。

为了优化查询效率，我们可以预处理信息。类似于前缀和，我们可以使用 前缀积 的思想。

前缀积数组

我们定义一个前缀积数组 $P$ ，其中 $P[i]$ 存储序列 $a$ 前 $i$ 个元素的乘积模 $10^9+7$ 的结果： [ P[i] = \prod_{k=1}^{i} a_k \pmod{10^9+7} ] 这个数组可以 $\mathcal{O}(n)$ 的时间内计算出来，递推公式为 $P[i] = (P[i-1] \cdot a_i) \pmod{10^9+7}$ ，并定义 $P[0] = 1$ 。
区间乘积计算

利用前缀积数组，区间 $[l, r]$ 的乘积可以表示为： [ \prod_{i=l}^{r} a_i = \frac{\prod_{i=1}^{r} a_i}{\prod_{i=1}^{l-1} a_i} = \frac{P[r]}{P[l-1]} ] 在模算术中，除以一个数等价于乘以这个数的 模逆元。设模数为 $M = 10^9+7$ 。区间乘积的计算就转换为： [ \left( P[r] \cdot (P[l-1])^{-1} \right) \pmod M ] 其中 $(P[l-1])^{-1}$ 是 $P[l-1]$ 关于模 $M$ 的乘法逆元。
求解模逆元

因为模数 $M = 10^9+7$ 是一个质数，我们可以根据 费马小定理 来求解模逆元。费马小定理指出，如果 $p$ 是一个质数，而整数 $a$ 不是 $p$ 的倍数，则有 $a^{p-1} \equiv 1 \pmod p$ 。

由此可推导出 $a^{p-2} \equiv a^{-1} \pmod p$ 。

所以， $(P[l-1])^{-1} \pmod M$ 可以通过计算 $(P[l-1])^{M-2} \pmod M$ 得到。这个幂运算可以通过 快速幂算法 在 $\mathcal{O}(\log M)$ 的时间内高效完成。
算法流程总结
- 预处理：用 $\mathcal{O}(n)$ 时间计算出前缀积数组 $P$ 。
- 查询：对于每个查询 $(l, r)$ ，用 $\mathcal{O}(\log M)$ 时间计算 $P[l-1]$ 的模逆元，然后与 $P[r]$ 相乘得到最终答案。
总的时间复杂度为 $\mathcal{O}(n + q \cdot \log M)$ ，空间复杂度为 $\mathcal{O}(n)$ ，能够满足性能要求。

代码

c++
java
python

#include <iostream>
#include <vector>

using namespace std;

// 定义模数
const int MOD = 1e9 + 7;

// 快速幂函数，计算 (base^exp) % MOD
long long power(long long base, long long exp) {
    long long res = 1;
    base %= MOD;
    while (exp > 0) {
        if (exp % 2 == 1) {
            res = (res * base) % MOD;
        }
        base = (base * base) % MOD;
        exp /= 2;
    }
    return res;
}

// 模逆元函数，计算 a^{-1} mod MOD
long long modInverse(long long n) {
    return power(n, MOD - 2);
}

int main() {
    int n, q;
    // 读取序列长度和查询数量
    cin >> n >> q;

    vector<long long> prefix_prod(n + 1, 1);
    for (int i = 1; i <= n; ++i) {
        long long val;
        cin >> val;
        // 计算前缀积
        prefix_prod[i] = (prefix_prod[i - 1] * val) % MOD;
    }

    vector<long long> results;
    for (int i = 0; i < q; ++i) {
        int l, r;
        cin >> l >> r;
        // 计算 P[l-1] 的模逆元
        long long inv_prefix_l_minus_1 = modInverse(prefix_prod[l - 1]);
        // 计算区间乘积
        long long ans = (prefix_prod[r] * inv_prefix_l_minus_1) % MOD;
        results.push_back(ans);
    }

    for (int i = 0; i < results.size(); ++i) {
        cout << results[i] << (i == results.size() - 1 ? "" : " ");
    }
    cout << endl;

    return 0;
}

import java.util.Scanner;
import java.util.ArrayList;
import java.util.List;

public class Main {
    // 定义模数
    private static final int MOD = 1_000_000_007;

    // 快速幂函数，计算 (base^exp) % MOD
    private static long power(long base, long exp) {
        long res = 1;
        base %= MOD;
        while (exp > 0) {
            if (exp % 2 == 1) {
                res = (res * base) % MOD;
            }
            base = (base * base) % MOD;
            exp /= 2;
        }
        return res;
    }

    // 模逆元函数，计算 n^{-1} mod MOD
    private static long modInverse(long n) {
        return power(n, MOD - 2);
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int q = sc.nextInt();

        long[] prefix_prod = new long[n + 1];
        prefix_prod[0] = 1;
        for (int i = 1; i <= n; ++i) {
            long val = sc.nextLong();
            // 计算前缀积
            prefix_prod[i] = (prefix_prod[i - 1] * val) % MOD;
        }

        List<Long> results = new ArrayList<>();
        for (int i = 0; i < q; ++i) {
            int l = sc.nextInt();
            int r = sc.nextInt();
            // 计算 P[l-1] 的模逆元
            long inv_prefix_l_minus_1 = modInverse(prefix_prod[l - 1]);
            // 计算区间乘积
            long ans = (prefix_prod[r] * inv_prefix_l_minus_1) % MOD;
            results.add(ans);
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < results.size(); ++i) {
            sb.append(results.get(i));
            if (i < results.size() - 1) {
                sb.append(" ");
            }
        }
        System.out.println(sb.toString());
    }
}

# 定义模数
MOD = 10**9 + 7

def main():
    # 读取序列长度和查询数量
    n, q = map(int, input().split())
    
    # 读取序列
    a = list(map(int, input().split()))

    # 计算前缀积
    prefix_prod = [1] * (n + 1)
    for i in range(n):
        prefix_prod[i + 1] = (prefix_prod[i] * a[i]) % MOD
    
    results = []
    for _ in range(q):
        l, r = map(int, input().split())
        
        # 使用 pow(base, exp, mod) 进行快速幂和模逆元计算
        # 计算 P[l-1] 的模逆元
        inv_prefix_l_minus_1 = pow(prefix_prod[l - 1], MOD - 2, MOD)
        
        # 计算区间乘积
        ans = (prefix_prod[r] * inv_prefix_l_minus_1) % MOD
        results.append(ans)
        
    print(*results)

if __name__ == "__main__":
    main()

算法及复杂度

算法：前缀积 + 模逆元 (费马小定理) + 快速幂
时间复杂度：预处理前缀积数组需要 $\mathcal{O}(n)$ 。每次查询需要通过快速幂计算模逆元，耗时 $\mathcal{O}(\log M)$ ，其中 $M$ 是模数。总共有 $q$ 次查询，因此总时间复杂度为 $\mathcal{O}(n + q \cdot \log M)$ 。
空间复杂度：需要一个数组来存储前缀积，所以空间复杂度为 $\mathcal{O}(n)$ 。