题目就是让求每次询问一个区间能否组成一个公差为 \(d\) 的等差数列。
首先我们可以算出一个等差数列的首项——求区间和然后逆推就好了。那么,我们如何判断一个区间可以组成这样一个等差数列?
考虑用一个哈希的 \(trick.\) 或者说,这个 trick 可以用来判定给定一个序列,问区间中某一个序列能否重排为该序列 的问题。
考虑对每个元素的 \(k\) 次方之和进行 “哈希” 。如果这个数列和原数列相同,那么其无论多少次方的和都应该是一样的。容易发现,不同的序列面对不同的 \(k\) 的贡献是不一样的,所以可以这样来判断。
时间复杂度就取决于 \(k\) 了,实际中选择了 \(k=\{1,2\}\) 然后套用等差数列平方求和公式即可。
别忘了取模。
#include<bits/stdc++.h>
using namespace std;
typedef double db;
#define int long long
const int mod=1e9+7;
const db eps=1e-10;
inline int Max(int x,int y){return x>y?x:y;}
inline int Min(int x,int y){return x<y?x:y;}
inline db Max(db x,db y){return x-y>eps?x:y;}
inline db Min(db x,db y){return x-y<eps?x:y;}
inline int Add(int x,int y,int M=mod){return (x+y)%M;}
inline int Mul(int x,int y,int M=mod){return 1ll*x*y%M;}
inline int Dec(int x,int y,int M=mod){return (x-y+M)%M;}
inline int Abs(int x){return x<0?-x:x;}
inline int read(){
int s=0,w=1;
char ch=getchar();
while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
while(isdigit(ch)){s=s*10+ch-'0';ch=getchar();}
return s*w;
}
inline void write(int x){
if(x<0)putchar('-'),x=-x;
if(x>9)write(x/10);
putchar(x%10+'0');
}
inline int qpow(int x,int y){
int res=1;
while(y){
if(y&1)res=Mul(res,x);
x=Mul(x,x);y>>=1;
}
return res;
}
typedef pair<int,int> pr;
#define fi first
#define se second
#define mk make_pair
#define pb emplace_back
#define poly vector<int>
const int N=2e5+10;
int n,q,a[N];
int f[N][2],inv2,inv6;
inline int inv(int x){return qpow(x,mod-2);}
inline int sum_sq(int x){
return Mul(inv6,Mul(x,Mul(x+1,Add(1,Mul(2,x)))));
}
inline int sum_1(int x){
return Mul(inv2,Mul(x,x+1));
}
int calc(int og,int d,int len){
int S2=0;
S2=Add(S2,Mul(Mul(d,d),sum_sq(len-1)));
S2=Add(S2,Mul(Mul(og,og),len));
S2=Add(S2,Mul(Mul(Mul(2,d),og),sum_1(len-1)));
return S2;
}
int calc1(int og,int d,int len){
return Add(Mul(og,len),Mul(d,sum_1(len-1)));
}
signed main(){
freopen("in.txt","r",stdin);
freopen("My.out","w",stdout);
n=read();q=read();
for(int i=1;i<=n;++i)a[i]=read();
for(int i=1;i<=n;++i){
f[i][0]=Add(f[i-1][0],a[i]);
f[i][1]=Add(f[i-1][1],Mul(a[i],a[i]));
}
inv2=inv(2);
inv6=inv(6);
// cout<<calc(2,4,1000)<<endl;
// cout<<calc1(2,4,3)<<endl;
int cnt=0;
while(q--){
++cnt;
int l=read(),r=read(),d=read();
if(l==r){
puts("Yes");
continue;
}
int len=(r-l+1);
int s1=Dec(f[r][0],f[l-1][0]);
int s2=Dec(f[r][1],f[l-1][1]);
int og=Mul(sum_1(len-1),d);
og=Dec(s1,og);
og=Mul(og,inv(len));
int S1=calc1(og,d,len);
if(S1!=s1){
puts("No");
continue;
}
int S2=calc(og,d,len);
if(S2!=s2){puts("No");}
else puts("Yes");
}
return 0;
}