CF1599F - Mars

· · 题解

CF1599F - Mars / 原题链接

解法

提供一个玄学做法。

设 len=r-l+1，相当于将序列重排成一个有 len 项且公差为 d 的序列。

找到一个 k，我们试着去维护这个等差序列的每个数字 k 次方的和，看看是否与原序列 k 次方的和相等。我们多取几个 k，使得错误性极小，如果都是相等的，就认为方案合法。（我取了 k=2,3,6,7,8,9）

容易结合小学奥数计算出，此等差序列的首项 \Large a=\frac{\sum\limits_{i=l}^rN_i-\frac{len*(len-1)*d}{2}}{len}。（N_i 指题面给的 i 号城市的距离）。

接下来我们要求 \sum\limits_{i=0}^{len-1}(a+di)^k=\sum\limits_{i=l}^r N_i^k。

等式右边很好计算，用前缀和即可。

用二项式定理，等式左边 \text{LHS}=\sum\limits_{j=0}^k\binom{k}{j}d^ja^{k-j}\sum\limits_{i=0}^{len-1} i^j。前面的和式是 O(k) 的，后面的和式可以用前缀和预处理，所以总共是 O(k) 的。

最后判断是否相等即可，时间复杂度 O(n+Tk)。

代码

（毒瘤码风）

#include<bits/stdc++.h>
#define rep(i,x,y) for(int i=x;i<=y;++i)
#define per(i,x,y) for(int i=x;i>=y;--i)
#define lon long long
#define pow BlankAo
using namespace std;
const int n7=201234,k7=12;
const lon mo=1000000007;
int n,T;lon a[n7],b[n7],s[n7][k7],inv[n7],pow[n7][k7],spow[n7][k7],C[k7][k7];

int rd(){
    int shu=0;bool fu=0;char ch=getchar();
    while( !isdigit(ch) ){if(ch=='-')fu=1;ch=getchar();}
    while( isdigit(ch) )shu=(shu<<1)+(shu<<3)+ch-'0',ch=getchar();
    return fu?-shu:shu;
}

lon Dpow(lon p,lon q){
    lon tot=1;
    while(q){
        if(q&1)tot=tot*p%mo;
        p=p*p%mo,q=q>>1;
    }
    return tot;
}

void ready(){
    rep(i,1,n)b[i]=1;
    rep(j,1,10)rep(i,1,n){
        b[i]=b[i]*a[i]%mo;
        s[i][j]=(s[i-1][j]+b[i])%mo;
    }

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

    rep(i,0,n)pow[i][0]=1;
    rep(i,1,n)rep(j,1,10)pow[i][j]=pow[i][j-1]*i%mo;
    rep(j,0,10)spow[0][j]=pow[0][j];
    rep(j,0,10)rep(i,1,n)spow[i][j]=(spow[i-1][j]+pow[i][j])%mo;

    rep(i,0,10)C[i][0]=1;
    rep(i,1,10)rep(j,1,i){
        C[i][j]=(C[i-1][j]+C[i-1][j-1])%mo;
    }
}

lon Dcalc(lon me,lon A,lon d,int r){
    lon tot=0;
    rep(i,0,me){
        tot=(tot+C[me][i]*Dpow(A,me-i)%mo*Dpow(d,i)%mo*spow[r][i]%mo)%mo;
    }
    return tot;
}

bool calc(lon A,lon d,int l,int r){
    int me;
    me=2;if( Dcalc(me,A,d,r-l)^( (s[r][me]-s[l-1][me]+mo)%mo ) )return 0;
    me=3;if( Dcalc(me,A,d,r-l)^( (s[r][me]-s[l-1][me]+mo)%mo ) )return 0;
    me=6;if( Dcalc(me,A,d,r-l)^( (s[r][me]-s[l-1][me]+mo)%mo ) )return 0;
    me=7;if( Dcalc(me,A,d,r-l)^( (s[r][me]-s[l-1][me]+mo)%mo ) )return 0;
    me=8;if( Dcalc(me,A,d,r-l)^( (s[r][me]-s[l-1][me]+mo)%mo ) )return 0;
    me=9;if( Dcalc(me,A,d,r-l)^( (s[r][me]-s[l-1][me]+mo)%mo ) )return 0;
    return 1;
}

int main(){
    n=rd(),T=rd();
    rep(i,1,n)a[i]=rd();
    ready();
    while(T--){
        lon l=rd(),r=rd(),d=rd();
        lon A=( (s[r][1]-s[l-1][1]+mo)%mo-(r-l+1)*(r-l)%mo*d%mo*inv[2]%mo+mo )%mo*inv[r-l+1]%mo;
        puts(calc(A,d,l,r)?"Yes":"No");
    }
    return 0;
}