[NOI2017]蚯蚓排队

第一行有两个正整数 n,m，分别表示蚯蚓的只数与操作次数。

第二行包含 n 个不超过 6 的正整数，依次表示编号为 1,2,…,n的蚯蚓的长度。

接下来 m 行，每行表示一个操作。每个操作的格式可以为：

1 i j（1≤i,j≤n）表示：令 i 号与 j 号蚯蚓所在的两个队伍合并为一个队伍，新队伍中， j 号蚯蚓紧挨在 i 号蚯蚓之后。保证在此操作之前， i 号蚯蚓在某个队伍的队尾， j 号蚯蚓在某个队伍的队首，且两只蚯蚓不在同一个队伍中。

2 i（1≤i≤n）表示：令 i 号蚯蚓与紧挨其后一个蚯蚓分离为两个队伍。保证在此操作之前， i 号蚯蚓不是某个队伍的队尾。

3 s k（k 为正整数，s 为一个长度至少为 k 的数字串）表示：询问 s 的每个长度为 k的子串 t 的 f(t) 的乘积，对 998244353 取模的结果。 f(t) 的定义见题目描述。

同一行输入的相邻两个元素之间，用恰好一个空格隔开。

C++11(clang++ 3.9) 解法, 执行用时: 1938ms, 内存消耗: 133736K, 提交时间: 2020-05-20 13:45:06

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<queue>
using namespace std;
#define ull unsigned long long
#define ll long long
#define RG register
#define MAX 222222
#define MOD 998244353
const int base=233;
inline int read(){
    RG int x=0,t=1;RG char ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
    if(ch=='-')t=-1,ch=getchar();
    while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
    return x*t;
}
char ch[10000010];
ull pw[MAX],has[MAX];
int nt[MAX],lt[MAX],a[MAX],g[MAX<<1];
int n,m;
const int mod=7654321;
struct Hash_Table{
    int h[mod],cnt;struct Line{int len,next,w;ull s;}e[10000000];
    void Add(int len,ull s,int w){
        int u=s%mod;
        for(int i=h[u];i;i=e[i].next)
            if(e[i].len==len&&e[i].s==s)
            {e[i].w=(e[i].w+w)%MOD;return;}
        e[++cnt]=(Line){len,h[u],w,s};h[u]=cnt;
    }
    int Query(int len,ull s){
        int u=s%mod;
        for(int i=h[u];i;i=e[i].next)
            if(e[i].len==len&&e[i].s==s)
                return e[i].w;
        return 0;
    }
}Hash;
void Link(int x,int y){
    nt[x]=y;lt[y]=x;
    ull ls=0;int tot=0;
    for(int i=x,len=49;i&&len;i=lt[i],--len){
        ull s=0;ls+=a[i]*pw[tot++];s=ls;int l=tot+1;
        for(int j=y;j&&l<=50;j=nt[j],++l)s=s*base+a[j],Hash.Add(l,s,1);
    }
}
void Cut(int x){
    int y=nt[x];ull ls=0;int tot=0;
    for(int i=x,len=49;i&&len;i=lt[i],--len){
        ull s=0;ls+=a[i]*pw[tot++];s=ls;int l=tot+1;
        for(int j=y;j&&l<=50;j=nt[j],++l)s=s*base+a[j],Hash.Add(l,s,MOD-1);
    }
    nt[x]=lt[y]=0;
}
int Query(int len){
    int l=strlen(ch+1),ret=1;ull s=0;
    for(int i=1;i<len;++i)s=s*base+ch[i]-48;
    ch[0]='0';
    for(int i=len;i<=l;++i){
        s=s*base+ch[i]-48;
        s-=pw[len]*(ch[i-len]-48);
        ret=1ll*ret*Hash.Query(len,s)%MOD;
    }
    return ret;
}
int main(){
    pw[0]=1;for(int i=1;i<MAX;++i)pw[i]=pw[i-1]*base;
    n=read();m=read();
    for(int i=1;i<=n;++i)Hash.Add(1,a[i]=read(),1);
    while(m--){
        int opt=read();
        if(opt==1){
            int x=read(),y=read();
            Link(x,y);
        }
        else if(opt==2){Cut(read());}
        else{
            scanf("%s",ch+1);int k=read();
            printf("%d\n",Query(k));
        }
    }
    return 0;
}

详情