题解 | 子数列求积

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static final long MOD = 1000000007L; // 模数 1e9+7

    public static void main(String[] args) throws IOException {
        // 高效读取输入（应对1e5量级数据）
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int q = Integer.parseInt(st.nextToken());

        // 前缀积数组（prefix[0]=1，prefix[1]=a1，prefix[2]=a1*a2...）
        long[] prefix = new long[n + 1];
        prefix[0] = 1;

        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= n; i++) {
            long num = Long.parseLong(st.nextToken());
            prefix[i] = (prefix[i - 1] * num) % MOD; // 预处理前缀积，每次取模
        }

        // 处理查询
        StringBuilder sb = new
        StringBuilder(); // 拼接输出，避免多次打印耗时
        for (int i = 0; i < q; i++) {
            st = new StringTokenizer(br.readLine());
            int l = Integer.parseInt(st.nextToken());
            int r = Integer.parseInt(st.nextToken());

            // 计算：prefix[r] * 逆元(prefix[l-1]) mod MOD
            long inv = pow(prefix[l - 1], MOD - 2); // 费马小定理求逆元
            long res = (prefix[r] * inv) % MOD;
            sb.append(res).append(" ");
        }

        // 输出结果（去掉最后一个空格）
        System.out.println(sb.toString().trim());
        br.close();
    }

    // 快速幂：计算 (base^exponent) mod MOD
    static long pow(long base, long exponent) {
        long res = 1;
        base = base % MOD; // 先取模，避免溢出
        while (exponent > 0) {
            if ((exponent & 1) == 1) { // 指数为奇数，乘上当前base
                res = (res * base) % MOD;
            }
            base = (base * base) % MOD; // 底数平方
            exponent >>= 1; // 指数除以2
        }
        return res;
    }
}