首页 > 试题广场 >

子数列求积

[编程题]子数列求积

热度指数：2532 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

$\hspace{15pt}$ 给定一个长度为 $n$ 的正整数序列 $\{a_1,a_2,\dots ,a_n\}$ 。接下来有 $q$ 次独立查询，第 $j$ 次查询给出一对下标 $l_j,r_j$ ，请你计算区间乘积

$\prod\limits_{i=l_j}^{r_j} a_i$

$\hspace{15pt}$ 并对模数 $10^9+7$ 取模后的结果。

输入描述:

第一行输入两个整数  ，分别表示序列长度与查询数量。
第二行输入  个整数  ，表示序列元素。
此后  行，第  行输入两个整数  ，表示一次查询的左右端点。

输出描述:

输出一行  个用空格隔开的整数，第  个整数为第  次查询的答案。

示例1

输入

输出

2 6 120

说明

区间  的乘积为 ； 的乘积为 ； 的乘积为 。

算法知识视频讲解

小男娘

发表于 2025-12-22 15:52:21

类似阶乘逆元预处理，预处理出所有前缀积以及前缀积逆元，然后回答每个询问，总时间复杂度。 #include <iostream> using namespace std; using ll = long long; const int MOD = 1e9 + 7; ll Pow(ll 展开全文

carson_flute

发表于 2026-01-15 22:25:38

本题是经典前缀积问题。核心思路核心观察定义前缀积数组 pref： pref[0] = 1 pref[i] = (a_1 \times a_2 \times \cdots \times a_i) \mod M 则区间乘积可表示为：但模运算中不能直接做除法！算法步骤前缀积表示正确展开全文

丨阿伟丨

发表于 2025-08-28 17:48:32

题目链接子数列求积题目描述给定一个长度为的正整数序列。接下来有次独立查询，第次查询给出一对下标 ()，请你计算区间乘积并对模数取模后的结果。解题思路本题要求我们高效地计算多次给定区间的乘积。如果对每次查询都遍历区间进行计算，在查询次数和区间长度都很大的情况下展开全文

此在Dasein

发表于 2026-01-13 01:13:57

算法：前缀积与逆元鉴于序列是静态的，前缀和思想的变体——前缀积是解决该问题的最优范式。核心逻辑定义前缀积数组表示从到的乘积。理论上，区间的乘积可以表示为：在模意义下转化为：零值处理为了解决导致的“信息坍缩”和“不可逆”问题，我们需要引入双层数据结构：非零展开全文

BeauWill

发表于 2026-01-13 01:59:19

题目是离线区间查询，想到使用前缀和比较合适。对于区间[l,r]的所有ai乘积，若暂不考虑取模，它的值应该等于区间[1,r]的所有ai乘积除以[1,l-1]的所有ai乘积即pre[r]/pre[l-1]。故预处理pre[i]表示前i个数相乘并模1E9+7的值。由于此题需要对1E9+7取模，因此查询时的展开全文