首页 > 试题广场 >

子数列求积

[编程题]子数列求积

热度指数：2478 时间限制：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)

_changbin

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
int fastpow(int x,int p){
    int ans=1;
    while(p){
        if(p&1) ans=ans*x%mod;
        x=x*x%mod;
        p>>=1;
    }
    return ans;
}
void solve(){
    int n,q;cin>>n>>q;
    vector<int> arr(n+1,1);
    for(int i=1;i<=n;i++) cin>>arr[i];
    vector<int> pre(n+1,1);
    for(int i=1;i<=n;i++) pre[i]=arr[i]*pre[i-1]%mod;
    while(q--){
        int l,r;cin>>l>>r;
        cout<<pre[r]*fastpow(pre[l-1],mod-2)%mod<<" ";
    }
}
signed main(){
    std::cin.tie(nullptr)->sync_with_stdio(false);
    int T = 1;
    // std::cin>>T;
    while(T--) solve();
    return 0;
}

发表于 2026-01-13 13:28:36 回复(0)

牛客203596504号

标准的模板题，就是把前缀和数组换成前缀积数组了而已。

要用到以下数学知识：

1. 模运算分配率：积的模等于模的积。
为了防止溢出，我们可以每做一次乘法就取一次模。
2. 模逆元：两数相乘取模为1就互为模逆元。
求区间积需要除法，但除法对于模运算没有分配律，我们就用乘以模逆元代替除法。
3. 费马小定理：如果p是质数，而a不是p的倍数，那么a^p-1MOD p = 1
题中的1000000007就是质数，所以模逆元modInverse(a, p) = a^p-2 MOD p

4. 快速幂算法：平方的平方的平方……，每次平方相当于指数翻倍，如果对应位是奇数就再乘一次。
因为费马小定理的指数极大，所以我们要快速计算它。

如果上面的介绍有误，望斧正。

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

C++

kilomatutinal

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const ll mod=1e9+7;

vector<ll> lie={1};

ll mo(ll a)
{
    ll ans=1;
    for(ll i=1e9+5;i>0;i/=2)
    {
        if((i&1)==1)
        {
            ans*=a;
            ans%=mod;
        }
        a*=a;
        a%=mod;
    }
    return ans;
}

int main() {
    int n,q;cin >> n >> q;
    ll f=1;
    for(int i=1;i<=n;i++)
    {
        ll num;cin >> num;
        f*=num;
        f%=mod;
        lie.push_back(f);
    }
    for(int i=0;i<q;i++)
    {
        ll l,r;cin >> l >> r;
        ll ans=lie[r]*mo(lie[l-1])%mod;
        cout << ans <<' ';
    }
}
/*
⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣠⣤⣤⣤⣤⣤⣤⣤⡀⠀⠀⠀⣾⡟⣻⣿⠇⠀⠀⠀⣠⣶⣶⣶⣶⣶⣤⣤⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⣠⡶⢾⣿⣿⣿⣿⣿⣿⣿⣿⣧⣤⣴⣶⡿⣿⡿⠷⢶⣶⣤⣤⣿⣿⣿⣿⣿⣿⣿⣿⣧⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⢰⡿⠁⠀⠀⠀⠉⢉⣩⣽⡿⠟⠋⠉⠀⠀⠀⠀⠀⠀⠀⠀⠈⠉⠛⠛⠿⣿⣿⣿⣿⣿⣿⣄⣀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⣠⣶⠿⣿⠇⠀⠀⠀⣠⣴⠿⠋⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠛⢷⣦⡉⠙⠛⠿⣶⣄⠀⠀⠀⠀⠀⠀
⠀⠀⢠⣿⠁⢸⡟⠀⠀⢠⣾⠟⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠉⢻⣦⡀⠀⠀⢻⡇⠀⠀⠀⠀⠀
⠀⠀⢸⡏⠀⢸⡇⠀⣰⡿⠃⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⡀⠀⠀⣠⡀⠀⠀⠀⠘⢿⣆⠀⢸⣇⠀⠀⠀⠀⠀
⠀⠀⣿⡇⠀⢸⣷⣼⡿⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣴⡄⠀⠀⠀⠀⠀⠀⣿⢿⣆⠀⣿⣧⡄⠀⠀⠀⠈⢻⣧⣿⣿⡇⠀⠀⠀⠀
⠀⠀⣿⡇⠀⠀⣿⡿⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⡾⠋⢻⣆⠀⠀⠀⠀⢰⡏⠀⠙⢷⣌⡉⠀⠀⡀⠀⠀⠀⢻⣿⢸⡇⠀⠀⠀⠀
⠀⢀⣿⢀⣤⣶⠟⠁⠀⠀⠀⠀⠀⠀⢰⡆⠀⠀⣠⣾⠏⠁⠀⠀⠙⢷⣦⣀⣴⠟⠀⠀⠀⠀⠙⠻⣦⣌⣿⠀⠀⠀⢨⣿⢸⡧⠀⠀⠀⠀
⠀⢸⣿⠈⠻⢷⡆⠀⠀⠀⠀⠀⠀⢀⣿⣣⣴⡾⠋⠀⣀⣤⡀⠀⠀⠀⠈⠙⠁⠀⠀⣤⣤⣀⠀⠀⠀⠙⣿⠂⠀⠀⢸⣯⢸⣿⠀⠀⠀⠀
⠀⣸⡇⠀⠀⢺⡇⠀⠀⠀⠀⠀⠀⢸⡏⠉⠁⣠⣴⣾⣿⠟⠃⠀⠀⣾⣿⠟⠀⠀⠀⠈⠻⣿⣷⣦⡀⠀⣿⢀⣀⠀⣸⡟⢸⣿⠀⠀⠀⠀
⠀⣿⡇⠀⠀⠸⣧⠀⣷⡀⠀⠀⠀⢸⣧⠀⠾⠿⠛⠉⠀⠀⠀⠀⢠⣿⣿⠃⠀⠀⠀⠀⠀⠀⠙⠿⠇⠘⣿⡟⠋⣠⡿⠁⢸⣿⠀⠀⠀⠀
⠀⣿⠁⠀⠀⠀⠻⣧⡸⣷⡀⠀⢀⣀⢻⣆⠀⠀⠀⠀⠀⠀⠀⠀⠘⠿⠃⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣴⣿⣡⣶⠟⠁⠀⢸⣿⠀⠀⠀⠀
⢸⡿⠀⠀⠀⠀⠀⠙⢿⣾⣷⣆⠈⠛⣿⡟⠀⣇⠀⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣴⡟⠋⠿⠛⠁⠀⠀⠀⠸⣿⠀⠀⠀⠀
⢸⡇⠀⠀⠀⠀⠀⠀⠀⠈⠉⠛⢿⣶⣾⡧⠀⠙⠚⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣿⡇⠀⠀⠀⠀⠀⠀⠀⠀⣿⠀⠀⠀⠀
⣿⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣾⡏⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢹⣧⠀⠀⠀⠀⠀⠀⠀⠀⣿⡇⠀⠀⠀
⣿⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣸⡿⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⡀⠀⠈⣿⡄⠀⠀⠀⠀⠀⠀⠀⢹⣧⠀⠀⠀
⡿⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣿⠇⠀⠀⠀⠀⠀⣦⠀⠀⠀⠀⢠⣶⠀⠀⣶⡄⠀⠀⠀⣸⡿⠀⠀⣿⡇⠀⠀⠀⠀⠀⠀⠀⠀⣿⡄⠀⠀
⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⣼⡟⠀⠀⠀⠀⠀⠀⢿⣧⡀⠀⢀⣼⡟⠀⠀⠘⠿⣶⣤⣶⠟⠁⠀⠀⢸⣷⠀⠀⠀⠀⠀⠀⠀⠀⠹⣷⠀⠀
⠁⠀⠀⠀⠀⠀⠀⠀⠀⢠⣿⠃⠀⠀⠀⠀⠀⠀⠀⠙⠻⠿⠟⠉⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠘⣿⡀⠀⠀⠀⠀⠀⠀⠀⠀⢿⣆⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⣼⡟⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣿⡇⠀⠀⠀⠀⠀⠀⠀⠀⠘⣿⡀
*/

发表于 2025-12-23 21:06:34 回复(3)

提交观点

问题信息

来自：2025年秋招-中国移...

难度：

4条回答 29收藏 232浏览

子数列求积

输入描述:

输出描述:

输入

输出

说明

问题信息

热门推荐

相关试题