题解 P3823 【[NOI2017]蚯蚓排队】

· · 题解

看到题解不多蒟蒻就来凑个数~

算法：哈希（似乎真的就只用这个？）

做这道题，你至少应该会哈希或者是 trie 的一种（做 NOI 的题真的不会哈希？），下面讲哈希解法。

对于这种题面巨长无比，数据范围极为磅礴的题，我们应该这样去解……

一、理清题意

简单地说就是最开始有一些长度为一的字符串，需要支持三种操作：

然后开始思考各种算法：SAM、AC自动机、trie……怎么好像都不行啊？！

二、观察数据范围

其实连那张表都不用看，这道题只要看总数据范围就好了。k\leq 50 ？？一个狡猾有效的方法：暴力。

直接维护出所有字符串的所有长度 50 以内的子串，链表暴力维护拼接和分裂，每一次计算拼接新产生的子串，或是分裂导致消失的子串。

对于子串的匹配我们可以想到用哈希，那么相当于要询问哈希值为某一个数的子串个数。值域太大开不了桶？在来一个哈希（哈希套哈希）。

三、写代码

那么可以开始写了，感觉代码也不是很难写，毕竟字符串滚动哈希和哈希表对于 NOI 选手来说应该算是很基础的东西了，即使是想笔者一样的蒟蒻也可以在 1h 内写出 88 分代码。

四、调整

然而交上去发现 TLE 了（如果是考场上就有点惨，没机会了），那么首先想到就是哈希表时间复杂度的问题。

一般来讲哈希表模数开大一点会更快，注意别MLE前提下开成大一点的质数就好。

那么我把模数改到 5056577 的时候就AC了。

下面是代码：

#include <bits/stdc++.h>
using namespace std;

typedef unsigned long long ull;

inline void read(int& x){
    char c=getchar();x=0;
    while(!isdigit(c))c=getchar();
    while(isdigit(c))x=x*10+c-'0',c=getchar();
}
inline int read(char *s){
    char c=getchar(); int len=0;
    while(!isdigit(c))c=getchar();
    while(isdigit(c))s[len++]=c,c=getchar();s[len]='\0';
    return len;
}

const int HASH_MOD=5056577, STA=1e7+5;
struct Hash_Table{
    int tot, hd[HASH_MOD+5], cnt[STA], nxt[STA];
    ull sta[STA];
    inline void mdf(ull _sta, int v){
        int res=_sta%HASH_MOD;
        for(int u=hd[res]; u; u=nxt[u]) if(sta[u]==_sta)
            return (void)(cnt[u]+=v);
        sta[++tot]=_sta, cnt[tot]=v;
        nxt[tot]=hd[res], hd[res]=tot;
    }
    inline int qry(ull _sta){
        int res=_sta%HASH_MOD;
        for(int u=hd[res]; u; u=nxt[u]) if(sta[u]==_sta)
            return cnt[u];
        return 0;
    }
}H;

const int N=2e5+5, K=55, LEN=1e7+5, Base=131, mod=998244353;

ull bin[K];
int n, m, a[N], lst[N], nxt[N], cnt[10];
char s[LEN];

inline void merge(int x, int y){
    nxt[x]=y, lst[y]=x;
    for(int k=2; k<=50; ++k){
        int l=0, r=0;
        for(int i=x; i&&l<k-1; i=lst[i]) ++l;
        for(int i=y; i&&l+r<k; i=nxt[i]) ++r;
        if(l+r<k) break;
        l=x;
        for(int i=1; i<=k-2&&lst[l]; ++i)
            l=lst[l];
        r=l;
        ull hash=0;
        for(int i=1; i<=k; ++i){
            hash=hash*Base+a[r];
            r=nxt[r];
        }
        while(true){
            H.mdf(hash, 1);
            if(l==x||!r) break;
            hash-=a[l]*bin[k-1];
            l=nxt[l];
            hash=hash*Base+a[r];
            r=nxt[r];
        }
    }
}
inline void split(int x, int y){
    for(int k=2; k<=50; ++k){
        int l=0, r=0;
        for(int i=x; i&&l<k-1; i=lst[i]) ++l;
        for(int i=y; i&&l+r<k; i=nxt[i]) ++r;
        if(l+r<k) break;
        l=x;
        for(int i=1; i<=k-2&&lst[l]; ++i)
            l=lst[l];
        r=l;
        ull hash=0;
        for(int i=1; i<=k; ++i){
            hash=hash*Base+a[r];
            r=nxt[r];
        }
        while(true){
            H.mdf(hash, -1);
            if(l==x||!r) break;
            hash-=a[l]*bin[k-1];
            l=nxt[l];
            hash=hash*Base+a[r];
            r=nxt[r];
        }
    }
    nxt[x]=lst[y]=0;
}
inline int query(char *s, int n, int k){
    int ans=1;
    if(k==1){
        for(int i=1; i<=n; ++i)
            ans=1ll*ans*cnt[s[i]-'0']%mod;
        return ans;
    }
    ull hash=0;
    for(int i=1; i<=k; ++i)
        hash=hash*Base+s[i]-'0';
    int l=1, r=k+1;
    while(true){
        ans=1ll*ans*H.qry(hash)%mod;
        if(r>n||!ans) break;
        hash-=(s[l++]-'0')*bin[k-1];
        hash=hash*Base+s[r++]-'0';
    }
    return ans;
}

int main(){
    bin[0]=1;
    for(int i=1; i<K; ++i)
        bin[i]=bin[i-1]*Base;

    read(n);read(m);
    for(int i=1; i<=n; ++i){
        read(a[i]);
        ++cnt[a[i]];
    }

    while(m--){
        int op, x, y, k;
        read(op);
        if(op==1){
            read(x);read(y);
            merge(x, y);
        }
        else if(op==2){
            read(x);
            split(x, nxt[x]);
        }
        else{
            x=read(s+1);read(k);
            printf("%d\n", query(s, x, k));
        }
    }

    return 0;
}

那么这题就做完了，感觉难度有些虚高（我才不会告诉你们我写NOI2017 d1t1整数的时候因为一个沙雕的+1调了3h呢），比 d1t1整数 更像是NOI2017的签到题？。