题面太长自己看吧orz。
参考：洛谷题解。
用链表暴力维护每个蚯蚓，每次合并和分离只对k*k的元素有影响，哈希一下存起来query时候比较就好了。
没了。
（具体复杂度我不会证明，以及bzoj卡空间，正常的哈希表空间总觉得不能开如代码所示的这么小。）
（自然溢出hash真的块）
#include#include #include #include #include #include #include #include using namespace std;typedef long long ll;typedef unsigned long long ull;const int N=2e5+5;const int K=50;const int mod=998244353;const int p=19260817;const int B=13;inline int read(){ int X=0,w=0;char ch=0; while(!isdigit(ch)){w|=ch=='-';ch=getchar();} while(isdigit(ch))X=(X<<3)+(X<<1)+(ch^48),ch=getchar(); return w?-X:X;}struct node{ int nxt,cnt; ll w;}e[21000000];char s[10000005];int n,m,cnt,head[p+5],t[10],a[N];int nxt[N],pre[N];ull f[K*2+5],base[K+5];inline void add(ull w,int on){ int u=w%p; for(int i=head[u];i;i=e[i].nxt){ if(e[i].w==w){ e[i].cnt+=on;return; } } e[++cnt].cnt=1;e[cnt].w=w;e[cnt].nxt=head[u];head[u]=cnt;}inline int ask(ull w){ int u=w%p; for(int i=head[u];i;i=e[i].nxt){ if(e[i].w==w)return e[i].cnt; } return 0;}void merge(int x,int y){ int l=K+1,r=K; memset(f,0,sizeof(f)); for(int i=x;i&&l>1;i=pre[i])f[--l]=a[i]; for(int j=y;j&&r<2*K;j=nxt[j])f[++r]=a[j]; for(int i=l;i<=r;i++)f[i]+=f[i-1]*B; for(int i=l;i<=K;i++){ for(int j=K+1;j<=min(r,i+K-1);j++){ add(f[j]-f[i-1]*base[j-i+1],1); } } nxt[x]=y;pre[y]=x;}void split(int x,int y){ int l=K+1,r=K; memset(f,0,sizeof(f)); for(int i=x;i&&l>1;i=pre[i])f[--l]=a[i]; for(int j=y;j&&r<2*K;j=nxt[j])f[++r]=a[j]; for(int i=l;i<=r;i++)f[i]+=f[i-1]*B; for(int i=l;i<=K;i++){ for(int j=K+1;j<=min(r,i+K-1);j++){ add(f[j]-f[i-1]*base[j-i+1],-1); } } nxt[x]=0;pre[y]=0;}int query(int k){ ll ans=1;ull val=0;int len=strlen(s+1); if(k==1) for(int i=1;i<=len;i++) ans=ans*t[s[i]-'0']%mod; else{ for(int i=1;i<=len;i++){ val=val*B+s[i]-'0'; if(i>k)val-=base[k]*(s[i-k]-'0'); if(i>=k)ans=ans*ask(val)%mod; } } return ans;}int main(){ n=read(),m=read(); base[0]=1; for(int i=1;i<=K;i++)base[i]=base[i-1]*B; for(int i=1;i<=n;i++){ a[i]=read();t[a[i]]++; } for(int i=1;i<=m;i++){ int op=read(); if(op==1){ int x=read(),y=read(); merge(x,y); } if(op==2){ int x=read(); split(x,nxt[x]); } if(op==3){ scanf("%s",s+1); int k=read(); printf("%d\n",query(k)); } } return 0;}
+++++++++++++++++++++++++++++++++++++++++++
+本文作者：luyouqi233。 +
+欢迎访问我的博客： +
+++++++++++++++++++++++++++++++++++++++++++