Nikkukun's Blog
0%

hihocoder1869 Items

发表于 更新于 分类于 ，

hihocoder

一句话题面：集合 \(S=\{a_i\}\)（\(|S| \leq 3 \times 10^5\)），\(q\) 次询问求是否存在一个子集 \(S_0\subseteq S\)，使得 \(\sum_{a_i\in S_0} a_i = r \pmod M\)（\(M \leq 3\times 10^5​\)）。

题解

具体请参考官方题解。

不得不说实在是很妙…… 在原有 DP 基础上为了加速转移，每次只更新可以更新的部分，跳过不能更新的部分。

每次加入元素 \(a_i\) 时，在一个可能是转移状态的位置之前，DP 数组的前缀是相同的，因此把 DP 数组当成字符串二分 LCP 长度就可以找到这个位置。不能转移的情况是，更新之前这一位就是 \(1\)，也就是没加入 \(a_i\) 时就可以取到了。

判断 LCP 用 Hash 即可，树状数组维护。这里学习到一个小技巧：普通 Hash 的 MOD 最好选择它的一个原根作做幂。记得提前算好原根的 \(n\) 次幂和对应的逆，不然就会像我一样疯狂 TLE。

复杂度证明十分地巧妙，通过等价代换分析出了总更新次数。另外，这套题的 B 题用了排序不等式证明复杂度。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
#include<cstdio>
#include<vector>
using namespace std;

const int N=300000+5,MOD=998244353,G=3;

typedef long long ll;
int f[N];

struct BITree{
    ll t[N];
    int Lowbit(int x){
        return x&-x;
    }
    void Add(int p,ll v){
        for(;p<N;p+=Lowbit(p))
            t[p]=(t[p]+v)%MOD;
    }
    ll Query(int p){
        ll ret=0;
        for(;p;p-=Lowbit(p))
            ret=(ret+t[p])%MOD;
        return ret;
    }
};

inline ll QPow(ll bas,ll t){
    ll ret=1;bas%=MOD;
    for(;t;t>>=1,bas=bas*bas%MOD)
        if(t&1LL)ret=ret*bas%MOD;
    return ret;
}

inline ll Inv(ll x){
    return QPow(x,MOD-2);
}

BITree t;
ll pow3[N],inv3[N];

void InitHash(){
    pow3[0]=1;
    for(int i=1;i<N;i++)
        pow3[i]=pow3[i-1]*G%MOD;
    for(int i=0;i<N;i++)
        inv3[i]=Inv(pow3[i]);
}

ll Hash(int l,int r){
    ll ret=(t.Query(r)-t.Query(l-1))%MOD;
    ret=ret*inv3[l-1]%MOD;
    return (ret+MOD)%MOD;
}

int n,m;
ll det;

inline bool Check(int st1,int st2,int M){
    ll h1=(Hash(st1,st1+M-1)+det)%MOD;
    ll h2=Hash(st2,st2+M-1);
    return h1==h2;
}

int BSearch(int L,int R,int st1,int st2){
    while(L<R){
        int M=(L+R)/2;
        if(Check(st1,st2,M))L=M+1;
        else R=M;
    }
    return L;
}

int q[N];

int main(){
    InitHash();
    scanf("%d%d",&n,&m);

    f[1]=1;
    t.Add(1,pow3[1]);

    for(int i=1,a,len;i<=n;i++){
        scanf("%d",&a);
        q[0]=0;		//q: update

        det=0;len=1;
        while(Check(1,1+a,m-a)==0){
            len=BSearch(len,m-a,1,1+a);
            if(f[len]==0&&f[a+len]==1)
                det=(det+pow3[len])%MOD;
            else{
                det=(det+MOD-pow3[len])%MOD;
                q[++q[0]]=a+len;
            }
        }

        det=0;len=1;
        while(Check(m-a+1,1,a)==0){
            len=BSearch(len,a,m-a+1,1);
            if(f[m-a+len]==0&&f[len]==1)
                det=(det+pow3[len])%MOD;
            else{
                det=(det+MOD-pow3[len])%MOD;
                q[++q[0]]=len;
            }
        }

        for(int j=1;j<=q[0];j++){
            t.Add(q[j],pow3[q[j]]);
            f[q[j]]=1;
        }
    }

    int nQ;
    scanf("%d",&nQ);
    while(nQ--){
        int r;
        scanf("%d",&r);
        printf(f[r+1]?"YES\n":"NO\n");
    }

    return 0;
}