Mars

等差数列可以用 \(gcd\) 来维护，这很显然。 但是本题有一个限制是取模，所以 \(gcd\) 直接寄了，换一个做法（类似于随机化的想法，就是说 \(k\) 次方的和相等，这样可以保证与顺序无关）。
推一下式子。
等式首项 $$a = \frac{\Sigma_{i=l}^r N_i-\frac{len\times (len-1) *d}{2}}{len}$$
知道首项之后就要求

二项式定理可以推得

Tips:
如果顺序无关，直接判断 \(k\) 次方和是否相等就行，正确性可以保证。

#include<bits/stdc++.h>
#define RG register
#define LL long long
#define U(x, y, z) for(RG int x = y; x <= z; ++x)
#define D(x, y, z) for(RG int x = y; x >= z; --x)
#define update(x, y) (x = x + y >= mod ? x + y - mod : x + y)
using namespace std;
const int mod = 1e9 + 7;
namespace FastIO {
#define il inline
const int iL = 1 << 25;
char ibuf[iL], *iS = ibuf + iL, *iT = ibuf + iL;
#define GC() (iS == iT) ? \
  (iT = (iS = ibuf) + fread(ibuf, 1, iL, stdin), (iS == iT) ? EOF : *iS++) : *iS++
void read(){}
template<typename _Tp, typename... _Tps>
void read(_Tp &x, _Tps &...Ar) {
    x = 0; char ch = GC(); bool flg = 0;
    for (; !isdigit(ch); ch = GC()) flg |= (ch == '-');
    for (; isdigit(ch); ch = GC()) x = (x << 1) + (x << 3) + (ch ^ 48);
    if (flg) x = -x;
    read(Ar...);    
}
char Out[iL], *iter = Out;
#define Flush() fwrite(Out, 1, iter - Out, stdout); iter = Out
template <class T>il void write(T x, char LastChar = '\n') {
    int c[35], len = 0;
    if (x < 0) {*iter++ = '-'; x = -x;}
    do {c[++len] = x % 10; x /= 10;} while (x);
    while (len) *iter++ = c[len--] + '0';
    *iter++ = LastChar; Flush();
}
template <typename T> inline void writeln(T n){write(n, '\n');}
template <typename T> inline void writesp(T n){write(n, ' ');}
inline char Getchar(){ char ch; for (ch = GC(); !isalpha(ch); ch = GC()); return ch;}
inline void readstr(string &s) { s = ""; static char c = GC(); while (isspace(c)) c = GC(); while (!isspace(c)) s = s + c, c = GC();}
}
using namespace FastIO;
struct modint{
    int x;
    modint(int o=0){x=o;}
    modint &operator = (int o){return x=o,*this;}
    modint &operator +=(modint o){return x=x+o.x>=mod?x+o.x-mod:x+o.x,*this;}
    modint &operator -=(modint o){return x=x-o.x<0?x-o.x+mod:x-o.x,*this;}
    modint &operator *=(modint o){return x=1ll*x*o.x%mod,*this;}
    modint &operator ^=(int b){
        if(b<0)return x=0,*this;
        b%=mod-1;
        modint a=*this,c=1;
        for(;b;b>>=1,a*=a)if(b&1)c*=a;
        return x=c.x,*this;
    }
    modint &operator /=(modint o){return *this *=o^=mod-2;}
    modint &operator +=(int o){return x=x+o>=mod?x+o-mod:x+o,*this;}
    modint &operator -=(int o){return x=x-o<0?x-o+mod:x-o,*this;}
    modint &operator *=(int o){return x=1ll*x*o%mod,*this;}
    modint &operator /=(int o){return *this *= ((modint(o))^=mod-2);}
    template<class I>friend modint operator +(modint a,I b){return a+=b;}
    template<class I>friend modint operator -(modint a,I b){return a-=b;}
    template<class I>friend modint operator *(modint a,I b){return a*=b;}
    template<class I>friend modint operator /(modint a,I b){return a/=b;}
    friend modint operator ^(modint a,int b){return a^=b;}
    friend bool operator ==(modint a,int b){return a.x==b;}
    friend bool operator !=(modint a,modint b){return a.x!=b.x;}
    bool operator ! () {return !x;}
    modint operator - () {return x?mod-x:0;}
};
template <typename T> inline void chkmin(T &x, T y){x = x < y ? x : y;}
template <typename T> inline void chkmax(T &x, T y){x = x > y ? x : y;}
template <typename T> inline T Min(T x, T y){return x < y ? x : y;}
template <typename T> inline T Max(T x, T y){return x > y ? x : y;}
inline void FO(string s){freopen((s + ".in").c_str(), "r", stdin); freopen((s + ".out").c_str(), "w", stdout);}

const int N = 2e5 + 10, M = 12;
int n, T;
modint a[N], b[N], s[N][M], inv[N], pw[N][M], spw[N][M], C[M][M];

modint Qpow(modint a, LL b) {
	modint res = 1;
	// cerr << "Chk " << a.x << " " << b << " "; 
	for (; b; b >>= 1) {
		if (b & 1) res *= a;
		a *= a;
	}
	// cerr << res.x << "\n";
	return res;
} 

inline void init() {
	U(i, 1, n) b[i] = 1;
	U(j, 1, 10) U(i, 1, n) {
		b[i] *= a[i];
		s[i][j] = s[i - 1][j] + b[i];
	}

	inv[1] = 1;
	U(i, 2, n) inv[i] = inv[mod % i] * (mod - mod / i);

	U(i, 0, n) pw[i][0] = 1;
	U(i, 1, n) U(j, 1, 10) pw[i][j] = pw[i][j - 1] * i;
	U(j, 0, 10) spw[0][j] = pw[0][j];
	U(j, 0, 10) U(i, 1, n) spw[i][j] = spw[i - 1][j] + pw[i][j];
	
	U(i, 0, 10) C[i][0] = 1;
	U(i, 1, 10) U(j, 1, i) C[i][j] = C[i - 1][j - 1] + C[i - 1][j];	
}

modint Dcalc(int k,modint A,modint d,int r){
	modint tot=0;
	U(i, 0, k){
		tot=(tot+C[k][i]*Qpow(A,k-i)*Qpow(d,i)*spw[r][i]);
		// cerr << C[k][i].x << " " << A.x << " " << Qpow(A, k - i).x << " " << Qpow(d, i).x << " " << spw[r][i].x << "\n";
	}
	return tot;
}

bool calc(modint A,modint d,int l,int r){
	int k;
	k=2;if( Dcalc(k,A,d,r-l)!=( (s[r][k]-s[l-1][k]) ) )return 0;
	k=3;if( Dcalc(k,A,d,r-l)!=( (s[r][k]-s[l-1][k]) ) )return 0;
	k=6;if( Dcalc(k,A,d,r-l)!=( (s[r][k]-s[l-1][k]) ) )return 0;
	k=7;if( Dcalc(k,A,d,r-l)!=( (s[r][k]-s[l-1][k]) ) )return 0;
	k=8;if( Dcalc(k,A,d,r-l)!=( (s[r][k]-s[l-1][k]) ) )return 0;
	k=9;if( Dcalc(k,A,d,r-l)!=( (s[r][k]-s[l-1][k]) ) )return 0;
	return 1;
}


int main(){
	//FO("");
	read(n, T);
	U(i, 1, n) read(a[i].x);
	init();
	while (T--) {
		int l, r; modint d;
		read(l, r, d.x);
		modint A = (s[r][1] - s[l - 1][1] - d * (r - l) * (r - l + 1) * inv[2]) * inv[r - l + 1];
		puts(calc(A, d, l, r) ? "Yes" : "No");
	}
	return 0;
}

原文地址：http://www.cnblogs.com/SouthernWay/p/16913751.html