首页 > 试题广场 >

子数列求积

[编程题]子数列求积
  • 热度指数：783 时间限制：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 取模后的结果。

输入描述:
\hspace{15pt}第一行输入两个整数 n,q\left(1 \leqq n,q \leqq 10^5\right) ，分别表示序列长度与查询数量。
\hspace{15pt}第二行输入 n 个整数 a_1,a_2,\dots ,a_n\left(1 \leqq a_i < 10^9+7\right) ，表示序列元素。
\hspace{15pt}此后 q 行，第 j 行输入两个整数 l_j,r_j\left(1 \leqq l_j \leqq r_j \leqq n\right) ，表示一次查询的左右端点。


输出描述:
\hspace{15pt}输出一行 q 个用空格隔开的整数，第 j 个整数为第 j 次查询的答案。
示例1

输入

5 3
1 2 3 4 5
1 2
1 3
2 5

输出

2 6 120

说明

区间 [1,2] 的乘积为 1\times2=2；[1,3] 的乘积为 1\times2\times3=6；[2,5] 的乘积为 2\times3\times4\times5 = 120。
算法知识视频讲解
开通博客
头像 Silencer76
发表于 2025-07-11 14:46:44
题目链接 HIGH18 子数列求积 题目描述 给定一个长度为 的正整数序列 和 次查询。每次查询给出一对 ()，要求计算子数列 的乘积，并对模数 取模。 输入描述: 第一行输入两个整数 。 第二行输入 个正整数 。 接下来 行，每行输入两个整数 。 输出描述: 输出一行，包含 个用 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 丨阿伟丨
发表于 2025-08-28 17:48:32
题目链接 子数列求积 题目描述 给定一个长度为 的正整数序列 。接下来有 次独立查询，第 次查询给出一对下标 ()，请你计算区间乘积 并对模数 取模后的结果。 解题思路 本题要求我们高效地计算多次给定区间的乘积。如果对每次查询都遍历区间 进行计算，在查询次数 和区间长度都很大的情况下 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 冷艳的西红柿刷牛客
发表于 2025-10-21 21:28:27
#include<iostream> #include<algorithm> using namespace std; typedef long long ll; const ll p = 1000000007; ll fast_pow_mod(ll base, ll 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

来自：2025年秋招-中国移...
难度：
0条回答 32浏览

热门推荐

相关试题

子数列求积

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号