【CF1599F】 Mars 题解

· · 题解

CF1599F 题解

前言

P3792 与这道题很类似，感兴趣的可以去做一做。

本人题解大多数通俗易懂，主要供蒟蒻食用，dalao 们不喜勿喷哦~ （其实我也是蒟蒻）

声明：数列哈希这条思路不是我本人想出来的，是上课的老师教我的。（就我这蒟蒻，这道题能想到哈希？）

题目大意

有一个序列 a，求 a 的一个区间 \left[l,r\right] 能否重排成为一个公差为 d 的等差数列。

解题方法

必备知识

哈希，快速幂，组合数等。第一个最重要，后面两个主要用来优化。

分析

首先，给定这个区间，我们可以求出区间和 S。那么，又知道公差 d，即可求出，如果该区间满足条件，必有首项

a=\dfrac{S-C_n^2d}{n}

那么，这个区间“应有的样子”也就知道了。只需判断这个区间“是否是应有的样子”即可。考虑用哈希。

显然，我们要设计的哈希函数 H，必须使得对应的序列里元素顺序不影响其函数值，类似交换律。

首先想到的当然是直接累加，即

H(l,r)=\sum_{i=l}^ra_i

但是这样容易冲突。考虑取每个元素的 k 次方之和。

H(l,r)=\sum_{i=l}^ra_i^k

这样，问题就解决了，并且还有

H(1,r)-H(1,l-1)=H(l,r)

所以，我们可以用类似前缀和的方式，求出每个区间实际的哈希值。但还有一个难点在于，如果每次询问都暴力算一遍该区间“应有的样子”的哈希值，那时间复杂度最坏 O(NQ)，妥妥 T 飞掉。

考虑等差数列 \{a,a+d,a+2d,\dots,a+(len-1)d\}。它对应的哈希值应该是

(a+0\cdot d)^k+(a+d)^k+(a+2d)^k+\cdots+\left[a+(len-1)d\right]^k

二项式展开得

\sum_{i=0}^kC_k^ia^i(0d)^{k-i}+\sum_{i=0}^kC_k^ia^i(1d)^{k-i}+\cdots+\sum_{i=0}^kC_k^ia^i\left[(len-1)d\right]^{k-i}

整理得

\sum_{j=0}^{len-1}\sum_{i=0}^kC_k^ia^i(jd)^{k-i}

交换 \sum 的位置并提公因式

\sum_{i=0}^kC_k^ia^id^{k-i}\sum_{j=0}^{len-1}j^{k-i}

不难发现，此时，只要预处理组合数 C 与 \sum_{j=0}^{len-1}j^{k-i} 的值就可以了。其余都能用快速幂计算。

所以，设

c_{i,j}=\sum_{l=0}^jl^i

特别地，c_{0,0}=1（这是为了处理 0^0 而特意加上的，否则会有错误）。

那么序列

\{a,a+d,a+2d,\dots,a+(len-1)d\}

对应的哈希值应该是

\sum_{i=0}^kC_k^ia^id^{k-i}c_{k-i,len-1}

时间复杂度：

预处理 c：O(Nk)。

预处理组合数：O(k)（这里吐槽一下，别的题解不知道为什么，一定要 O(k^2) 求，直接用公式 C_n^i=C_n^{i-1}\cdot\dfrac{n-i+1}{i} 就行了，O(k) 的复杂度基本可以忽略）。

单次询问：O(k)。

总时间复杂度：O(\ (N+Q)k)。如果硬是要算上快速幂的时间的话，那就是 O(\ (N+Q)k\log_2(mod)\ )，大约再乘个 20，其实也没必要。

代码

最终的时间复杂度，就取决于 k 了。这里取 k=37。

#include <bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
const int N=2e5+5;
int qpow(int x,int y){
    int res=1;
    while(y){
        if(y&1) res=1ll*res*x%mod;
        y>>=1;
        x=1ll*x*x%mod;
    }
    return res;
}
const int K=37;
int C[K+5];//C[i] 表示 C(K,i)
int n,Q,s[N];
int ss[N],c[K+5][N];
int main(){
    scanf("%d%d", &n, &Q);
    for(int i=1;i<=n;i++){
        scanf("%d",&s[i]);
        s[i]=(s[i]+114514)%mod;//防卡技巧之同时加个东西，不影响结果
    }
    c[0][0]=1;
    for(int i=1;i<=n;i++){
        int tmp=1;
        for(int j=0;j<=K;j++,tmp=1ll*tmp*i%mod)
            c[j][i]=(c[j][i-1]+tmp)%mod;
        ss[i]=(ss[i-1]+qpow(s[i],K))%mod;//“前缀哈希和”处理
        s[i]=(s[i]+s[i-1])%mod;//前缀和处理
    }
    C[0]=1;
    for(int i=1;i<=K;i++)
        C[i]=C[i-1]*1ll*(K-i+1)%mod*qpow(i,mod-2)%mod;
    while(Q--){
        int x,y,d;
        scanf("%d%d%d",&x,&y,&d);
        int len=y-x+1,sum=(s[y]-s[x-1]+mod)%mod;
        int st=1ll*(sum-1ll*len*(len-1)/2%mod*d%mod+mod)%mod*qpow(len,mod-2)%mod;
        int res=0;
        for(int i=0;i<=K;i++)
            res=(res+1ll*C[i]*qpow(st,i)%mod*qpow(d,K-i)%mod*c[K-i][len-1]%mod)%mod;
        if(res==(ss[y]-ss[x-1]+mod)%mod) printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}

经作者亲身试验，可放心食用。