B3645 数列前缀和 20

news/2024/10/18 5:56:02/

题目描述

给定一个长度为 n 的数列 a，请回答 q 次询问，每次给定 l,r，请求出 ( $\prod_{r}^{i=l}a[i]$ )mod p 的值，其中 p=1,145,141。

输入格式

第一行是两个整数，依次表示数列长度 n 和询问次数 q。
第二行有 n 个整数，第 i 个整数表示 ai。
接下来 q 行，每行两个整数 l,r，表示一次询问。

输出格式

为了避免大量数据输出导致超时，请输出一行一个整数表示所有询问的答案的按位异或和。

输入输出样例

输入 #1复制

输出 #1复制

说明/提示

样例 1 解释

三次询问的答案依次为 6,12,24，按位异或和为 18。

数据规模与约定

对于 30% 的数据，保证 n,q≤10^3。
对于60% 的数据，保证 n,q≤10^5。

对于全部的测试点，保证 1≤n,q≤10^6，1≤l≤r≤n，1≤ai<p。

提示

你可以在这里学习如何线性求逆元，请尽可能做到 O(1) 回答单次询问。

本题先求到n的前缀积，然后维护l-1的前缀积，r+1的后缀积，对l-1的前缀积，r+1的后求逆，

最后相乘再取模，欧克

#include<bits/stdc++.h>
using namespace std;
//#pragma GCC optimize(2)
#define  endl '\n'
#define lowbit(x) ((x)&-(x))
#define pi 3.1415926535
const int mod=1145141;
typedef long long ll;
ll ans=0,n1,m1;
ll t=0,s1=0,s2=0,s3=0,s4=0,max1=0,max2=0,w,min1=100000000,sum=0,n,m,i,j,k,v,l,r;inline int read() {bool sym=0;int res=0;char ch=getchar();while(!isdigit(ch))sym |=(ch =='-'),ch=getchar();while(isdigit(ch)) res =(res<<3)+(res<<1)+(ch^48),ch=getchar();return sym ? -res : res;
}
void print(int x) {if(!x)return;print(x/10);putchar(x%10+'0');
}ll exgcd(ll a,ll b,ll &x,ll &y) {if(b==0) {x=1,y=0;return a;}ll d=exgcd(b,a%b,y,x);y-=a/b*x;return d;
}ll cc(ll a) {ll x,y;exgcd(a,mod,x,y);return (x%mod+mod)%mod;
}
ll a[1000086],b[1000869],c[1000860];
ll inv[1000860];
void invv(ll n){inv[0]=1;for(i=1;i<=n;i++){inv[i]=(mod-mod/a[i])*inv[mod%a[i]]%mod;}}
int main() {ll q;ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin>>n>>q;for(i=1;i<=n;i++)cin>>a[i];invv(n);b[0]=1;c[n+1]=1;for(i=1;i<=n;i++){b[i]=b[i-1]*a[i]%mod;}for(i=n;i>=1;i--){c[i]=c[i+1]*a[i]%mod;}s1=b[n];// 前缀积 ans=0; while(q--){cin>>l>>r;s2=cc(b[l-1]);s3=cc(c[r+1]);//cout<<s2<<" "<<s3<<endl;//	cout<<s1*s2*s3%mod<<endl;ans^=s1*s2*s3%mod;}cout<<ans;return 0;
}//mio lover