题目描述
nocriz是个友善的出题人。
有(n)个数(a_1,a_2,...,a_n),有(q)次询问,每次问(a_l imes a_l+1 imes ... imes a_r) (mod) (998244353) 的值。
输入格式
第一行一行两个整数(n,q)。
第二行一行(n)个整数(a_1,a_2,...,a_n)。
接下来(q)行,每行两个整数(l_i,r_i)。
输出格式
输出(q)行,每行一个整数,代表答案。
数据范围
(1leq n,q leq 2*10^5)
(1leq a_i leq 998244352)
思路
很显然这是一道大水题,解决的办法也有很多,比如说用线段树等数据结构,这里就不细说了。更简单的方法是利用前缀和思想。(Ans(l,r)=pre[r]/pre[l-1])。
众所周知,带模数时不能直接除,要用乘法逆元,我这里使用的是扩展欧几里得算法。
代码
#include<cstdlib>
#include<algorithm>
#define mod 998244353
#define ll long long
#define maxn (int)(2*1e5+10)
ll a[maxn],X,Y;
using namespace std;
void exgcd(ll m,ll n){
if(!n){
X=1,Y=0;
return;
}
exgcd(n,m%n);
ll t=X;
X=Y;
Y=t-m/n*Y;
return;
}
ll inv(ll t){
exgcd(mod,t);
return (Y+mod)%mod;
}
int main(){
int n,i,l,r,q;
ll x,ans;
a[0]=1;
scanf("%d%d",&n,&q);
for(i=1;i<=n;i++){
scanf("%lld",&x);
a[i]=a[i-1]*x%mod;
}
for(i=1;i<=q;i++){
scanf("%d%d",&l,&r);
ans=a[r]*inv(a[l-1])%mod;
printf("%lld
",ans);
}
return 0;
}