首页 > 试题广场 >

子数列求积

[编程题]子数列求积

热度指数：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

说明

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

算法知识视频讲解

Python3

驴主

前缀数组 + 乘法逆元

Python 写起来简单。

from functools import cache
from itertools import accumulate

MOD = int(1e9 + 7)

n, q = map(int, input().split())
arr = list(map(int, input().split()))
pre = list(accumulate(arr, lambda a, b: a * b % MOD))
pre.append(1)

@cache
def inverse(x):
    return pow(x, MOD - 2, MOD)

def divide(a, b):
    return a * inverse(b) % MOD 

ans = []
for _ in range(q):
    l, r = map(int, input().split())
    ans.append(divide(pre[r - 1], pre[l - 2]))

print(' '.join(str(x) for x in ans))

发表于 2026-01-13 16:26:26 回复(0)