子数列求积【牛客tracker 每日一题】

子数列求积

时间限制：1秒 空间限制：256M

网页链接

牛客tracker

牛客tracker & 每日一题，完成每日打卡，即可获得牛币。获得相应数量的牛币，能在【牛币兑换中心】，换取相应奖品！助力每日有题做，丰盈牛币日益多！

题目描述

给定一个长度为n nn的正整数序列 {a 1 , a 2 , … , a n a_1,a_2,…,a_na1​,a2​,…,an​} 。接下来有q qq次独立查询，第j jj次查询给出一对下标l j , r j l_j,r_jlj​,rj​，请你计算区间乘积

∏ i = l j r j a i ∏_{i=l_j}^{r_j}a_i∏i=lj​rj​​ai​​

并对模数10 9 + 7 10^9+7109+7取模后的结果。

输入描述：

第一行输入两个整数n , q ( 1 ≦ n , q ≦ 10 5 ) n,q(1≦n,q≦10^5)n,q(1≦n,q≦105)，分别表示序列长度与查询数量。
第二行输入n nn个整数a 1 , a 2 , … , a n ( 1 ≦ a i < 10 9 + 7 ) a_1,a_2,…,a_n(1≦a_i<10^9+7)a1​,a2​,…,an​(1≦ai​<109+7)，表示序列元素。
此后q qq行，第j jj行输入两个整数l j , r j ( 1 ≦ l j ≦ r j ≦ n ) l_j,r_j(1≦l_j≦r_j≦n)lj​,rj​(1≦lj​≦rj​≦n)，表示一次查询的左右端点。

输出描述：

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

示例1

输入：

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

输出：

2 6 120

说明：

区间[ 1 , 2 ] [1,2][1,2]的乘积为1 × 2 = 2 1×2=21×2=2；[ 1 , 3 ] [1,3][1,3]的乘积为 1×2×3=6；[ 2 , 5 ] [2,5][2,5]的乘积为2 × 3 × 4 × 5 = 120 2×3×4×5=1202×3×4×5=120。

解题思路

本题采用前缀积结合费马小定理+快速幂求逆元的方法求解区间乘积模运算问题，模数10 9 + 7 10^9+7109+7是质数；首先初始化前缀积数组s u m ， s u m [ 0 ] = 1 ， s u m [ i ] sum，sum[0]=1，sum[i]sum，sum[0]=1，sum[i]存储序列前i项元素的乘积对模数取模的结果，遍历序列完成O ( n ) O(n)O(n)的前缀积预处理；编写快速幂函数f p fpfp，实现高效的幂次取模计算；根据费马小定理，质数模数下a aa的乘法逆元为a p − 2 m o d p a^{p-2} \mod pap−2modp，因此区间[ l , r ] [l,r][l,r]的乘积等于( s u m [ r ] × f p ( s u m [ l − 1 ] , p − 2 ) ) m o d p (sum[r] × fp(sum[l-1], p-2)) \mod p(sum[r]×fp(sum[l−1],p−2))modp；对每组查询直接套用公式计算结果，单次查询耗时O ( l o g p ) O(logp)O(logp)。该方法总时间复杂度O ( n + q l o g p ) O(n+qlogp)O(n+qlogp)，完美适配n 、 q ≤ 10 5 n、q≤10^5n、q≤105的规模，高效且精准完成所有区间乘积的模运算查询。

代码内容

#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;typedefunsignedlonglongull;typedefpair<ll,ll>pii;constll p=1e9+7;constll N=1e5+10;ll a[N],sum[N];llfp(ll a,ll b){ll ans=1;while(b){if(b&1)ans=ans*a%p;a=a*a%p;b>>=1;}returnans;}intmain(){ll T=1;while(T--){ll n,q;cin>>n>>q;sum[0]=1;for(ll i=1;i<=n;i++){cin>>a[i];sum[i]=sum[i-1]*a[i]%p;}while(q--){ll l,r;cin>>l>>r;cout<<sum[r]*fp(sum[l-1],p-2)%p<<" ";}}return0;}