P8270 题解

_lbw_ · 2023-09-16 13:00:16 · 个人记录

设 r=|\sum|

自古道 \mathcal{O}(r^2|S|) 可过，我言 \mathcal{O}(r|S|+2^{r}) 也可过。

看到字符集只有 18，联想到求出所有答案。

我们考虑什么样的询问是可以的，容易发现应该要满足对于询问中的每一个字母，找到所有这个字母的出现位置，然后两个串相邻这个字母隔的字母数量相同。

我们发现不好做，考虑哈希。

这实际上是两个序列的比较问题，我们看成两个列向量，然后随机一个行向量去乘他们，考虑是否算出来的答案相同。

于是我们先枚举一个字母，然后随机一个行向量。

然后另外的字母算出如果选他们对答案的贡献，总答案就是选出字母的和，直接计算即可。

然后判断一下两个串算出来的答案是否相同，贡献一下答案数组就可以了。

#include <set>
mt19937 rnd(her1);
const int maxn = 1e5+5;
ll q,hshs[1<<18],hsht[1<<18],S;
char s[maxn],t[maxn];bitset<1<<18>bit;
ll pos[maxn],val[maxn],tot,bel[maxn],vc[26],lg[1<<18];
ll get_Hash(char c,char*K,ll n,ll*hsh){
    mem(vc,0);tot=0;
    F(i,1,n)if(K[i]==c)pos[bel[i]=++tot]=i;else bel[i]=tot+1;
    F(c2,'a','r')F(i,1,n)if(K[i]==c2&&bel[i]!=tot+1)vc[c2-'a']+=val[bel[i]];
    F(s,1,S)hsh[s]=(hsh[s^(s&-s)]+vc[lg[s&-s]])%cht;return tot;
}
char qr[233];
int main(){
    // freopen("1.in","r",stdin);
    // freopen("1.out","w",stdout);
    scanf("%s%s",s+1,t+1);q=read();S=(1<<18)-1;
    F(i,0,17)lg[(1<<i)]=i;F(s,0,S)bit[s]=1;ll n=max(strlen(s+1),strlen(t+1));
    F(c,'a','r'){
        F(i,1,n)val[i]=rnd()%cht;
        ll L1=get_Hash(c,s,strlen(s+1),hshs);
        ll L2=get_Hash(c,t,strlen(t+1),hsht);
        F(s,0,S)if(hshs[s]!=hsht[s]||L1!=L2)bit[s|(1<<c-'a')]=0;
    }
    while(q--){
        scanf("%s",qr);ll p=strlen(qr);
        ll s=0;F(i,0,p-1)s|=(1<<qr[i]-'a');
        putchar(bit[s]?'Y':'N');
    }
    return 0;
}//1h11mins