zcmimi's blog
查看原题

点击跳转

可以发现110\leftrightarrow 011相当于0前/后移动了2格,那么每个0位置的奇偶性是不变的

而且每个0无法移动到下一个0的后面

把这些0记录到一个序列里,然后通过哈希判断两个子串在序列中对应的部分是否相同

因为子序列的起点奇偶性不同,分别表示以起点为奇数和偶数为标准时哈希得的前缀0序列数组。

#include<cstdio>
const int N=200011,P=998244353;
int n,q,s[N],b[N],h[N],H[N];
char a[N];
int get(int l,int r){
    int*g=(l&1)?h:H;
    return (g[r]-1ll*g[l-1]*b[s[r]-s[l-1]]%P+P)%P;
}
int main(){
    scanf("%d%s%d",&n,a+1,&q);
    b[0]=1;
    for(int i=1;i<=n;++i){
        b[i]=23ll*b[i-1]%P;
        s[i]=s[i-1]+(a[i]==48);
        if(a[i]==48)
            h[i]=(23ll*h[i-1]+1+(i&1))%P,
            H[i]=(23ll*H[i-1]+1+(i&1^1))%P;
        else h[i]=h[i-1],H[i]=H[i-1];
    }
    while(q--){
        int x,y,w;
        scanf("%d%d%d",&x,&y,&w);
        printf(get(x,x+w-1)==get(y,y+w-1)?"Yes\n":"No\n");
    }
}
LG CF1320D Reachable Strings
comment评论
Search
search