题解 | #子数列求积#

题目链接

题目描述

给定一个长度为 $n$ 的正整数序列 $a$ 和 $q$ 次查询。每次查询给出一对 $l, r$ ( $1 \le l \le r \le n$ )，要求计算子数列 $a_l, \dots, a_r$ 的乘积，并对模数 $10^9 + 7$ 取模。

输入描述: 第一行输入两个整数 $n, q$ 。第二行输入 $n$ 个正整数 $a_1, \dots, a_n$ 。接下来 $q$ 行，每行输入两个整数 $l, r$ 。

输出描述: 输出一行，包含 $q$ 个用空格隔开的整数，表示每次查询的结果。

解题思路

本题是区间查询问题。对于每次查询，如果都遍历区间 $[l, r]$ 计算乘积，总时间复杂度为 $\mathcal{O}(n \cdot q)$ ，会超时。我们需要更高效的方法。

前缀积 + 模逆元

我们可以借鉴前缀和的思想，使用 前缀积。

预处理前缀积数组：我们创建一个数组 prefix_prod，其中 prefix_prod[i] 存储序列前 $i$ 个数的乘积对 $m=10^9+7$ 取模的结果。
- $prefix\_prod[0] = 1$
- $prefix\_prod[i] = (prefix\_prod[i-1] \cdot a_i) \pmod m$ 这个预处理过程的时间复杂度为 $\mathcal{O}(n)$ 。
回答查询：对于任意区间 $[l, r]$ 的乘积，可以用前缀积数组计算得出： $Product(l, r) = \frac{prefix\_prod[r]}{prefix\_prod[l-1]} \pmod m$

在模算术中，除以一个数等于乘以它的 模逆元。因为模数 $m=10^9+7$ 是一个质数，所以可以根据 费马小定理 求逆元： $(prefix\_prod[l-1])^{-1} \equiv (prefix\_prod[l-1])^{m-2} \pmod m$

因此，原式变为： $Product(l, r) \equiv prefix\_prod[r] \cdot (prefix\_prod[l-1])^{m-2} \pmod m$

计算幂次的部分可以使用 快速幂 算法，其时间复杂度为 $\mathcal{O}(\log m)$ 。

算法步骤总结:

定义模数 $m = 10^9 + 7$ 。
实现一个快速幂函数 power(base, exp)，它在模 $m$ 下计算。
读入 $n$ 和 $q$ 。
创建大小为 $n+1$ 的前缀积数组 prefix_prod，并用 $\mathcal{O}(n)$ 的时间复杂度完成填充。
循环 $q$ 次，对于每次查询 $(l, r)$ : a. 计算 prefix_prod[l-1] 的模逆元 inv = power(prefix_prod[l-1], m - 2)。 b. 计算结果 ans = (prefix_prod[r] * inv) % m。 c. 将 ans 存入结果列表。
输出结果列表。

整体复杂度:

时间复杂度： $\mathcal{O}(n + q \log m)$ 。
空间复杂度： $\mathcal{O}(n)$ 。

代码

cpp
java
python

#include <iostream>
#include <vector>

using namespace std;

const int MOD = 1e9 + 7;

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;
}

long long modInverse(long long n) {
    return power(n, MOD - 2);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, q;
    cin >> n >> q;

    vector<long long> prefix_prod(n + 1);
    prefix_prod[0] = 1;
    for (int i = 1; i <= n; ++i) {
        long long a;
        cin >> a;
        prefix_prod[i] = (prefix_prod[i - 1] * a) % MOD;
    }

    vector<long long> results;
    for (int i = 0; i < q; ++i) {
        int l, r;
        cin >> l >> r;
        long long numerator = prefix_prod[r];
        long long denominator_inv = modInverse(prefix_prod[l - 1]);
        results.push_back((numerator * denominator_inv) % MOD);
    }

    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 {
    static final int MOD = 1_000_000_007;

    public 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;
    }

    public 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[] prefixProd = new long[n + 1];
        prefixProd[0] = 1;
        for (int i = 1; i <= n; i++) {
            long a = sc.nextLong();
            prefixProd[i] = (prefixProd[i - 1] * a) % MOD;
        }

        List<Long> results = new ArrayList<>();
        for (int i = 0; i < q; i++) {
            int l = sc.nextInt();
            int r = sc.nextInt();
            long numerator = prefixProd[r];
            long denominatorInv = modInverse(prefixProd[l - 1]);
            results.add((numerator * denominatorInv) % MOD);
        }

        for (int i = 0; i < results.size(); i++) {
            System.out.print(results.get(i) + (i == results.size() - 1 ? "" : " "));
        }
        System.out.println();
    }
}

MOD = 10**9 + 7

def power(base, exp):
    res = 1
    base %= MOD
    while exp > 0:
        if exp % 2 == 1:
            res = (res * base) % MOD
        base = (base * base) % MOD
        exp //= 2
    return res

def mod_inverse(n):
    return power(n, MOD - 2)

def solve():
    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())
        numerator = prefix_prod[r]
        denominator_inv = mod_inverse(prefix_prod[l - 1])
        results.append((numerator * denominator_inv) % MOD)
        
    print(*results)

solve()

算法及复杂度

算法：前缀积 + 模逆元 (使用快速幂)
时间复杂度： $\mathcal{O}(N + Q \log M)$ ，其中 $N$ 是序列长度, $Q$ 是查询次数, $M$ 是模数。
空间复杂度： $\mathcal{O}(N)$ ，用于存储前缀积数组。