【题目】#2303. 「NOI2017」蚯蚓排队

【题意】给定n条长度不超过6的蚯蚓，初始各自在一个队伍。m次操作：1.将i号蚯蚓和j号蚯蚓的队伍合并（保证i为队尾，j为队首）。2.将i号蚯蚓和它后面的蚯蚓分离成两个队。3.询问：给定字符串S和正整数k，求f(每个长度为k的子串)的乘积。其中f(S)定义为蚯蚓在其队伍向后延伸k位组成的字符串等于S的蚯蚓个数。\(n \leq 2*10^5,m \leq 5*10^5,k \leq 50,\sum |s| \leq 10^7,c \leq 10^3\)，其中c为操作2的数量。

【算法】模拟+hash

【参考】LZZの知乎回答

暴力一点考虑，每个队伍维护一条链，合并和分裂时维护\(c_{x,i}\)表示第x号蚯蚓向后延伸i位的字符串hash值并更新长度为i的答案，查询的时候直接枚举子串访问长度为i的答案中hash值相同的。

容易知道这样最坏复杂度是\(O(mk^2+\sum |s|)\)，理论上依然无法通过。

继续分析。

考虑分离操作至多c次，复杂度为\(O(ck^2)\)。

考虑合并操作，因为每次合并其实显然是不需要枚举满的，是否有可能省去一个k的复杂度？合并的终串中每个子串只会被统计一次（分离只有1000次，不影响复杂度），而总共有nk个子串，所以复杂度为\(O(nk)\)。

总复杂度\(O(ck^2+nk+\sum |s|)\)。

注意：我用的hash方式是一个小哈希存邻接表，一个大哈希当成真实值来检验。

#include<cstdio>

#include<cstring>

#include<algorithm>

#define ll long long

bool isdigit(char c){return c>='0'&&c<='9';}

int read(){

	int s=0,t=1;char c;

	while(!isdigit(c=getchar()))if(c=='-')t=-1;

	do{s=s*10+c-'0';}while(isdigit(c=getchar()));

	return s*t;

}

using namespace std;

const int maxn=200010,MOD=998244353,cmod=3000007,dmod=1000000007,basec=233,based=123,maxk=60,maxL=10000010;

int first[cmod+5],tot,n,m,a[maxL],b[maxL],E[maxk],f[maxk],A[maxn],c[maxn][maxk],d[maxn][maxk],nxt[maxn],pre[maxn];

char s[maxL];

struct edge{int k,v,x,from;}e[maxn*maxk];

void insert(int k,int u,int v,int x){

	for(int i=first[u];i;i=e[i].from)if(e[i].k==k&&e[i].v==v){

		e[i].x+=x;

		return;

	}

	e[++tot]=(edge){k,v,x,first[u]};first[u]=tot;

}

int cM(int x){return x>=cmod?x-cmod:x;}

int dM(int x){return x>=dmod?x-dmod:x;}

int main(){

	n=read();m=read();

	E[0]=1;for(int i=1;i<=50;i++)E[i]=1ll*E[i-1]*basec%cmod;

	f[0]=1;for(int i=1;i<=50;i++)f[i]=1ll*f[i-1]*based%dmod;

	for(int i=1;i<=n;i++){

		A[i]=read();

		c[i][1]=d[i][1]=A[i];

		insert(1,A[i],A[i],1);//

	}

	while(m--){

		int kind=read();

		if(kind==1){

			int x=read(),y=read();

			nxt[x]=y;pre[y]=x;

			for(int i=1;i<50&&x;i++){

				int z=y;

				for(int j=1;i+j<=50&&z;j++){

					c[x][i+j]=(1ll*c[x][i+j-1]*basec+A[z])%cmod;

					d[x][i+j]=(1ll*d[x][i+j-1]*based+A[z])%dmod;

					insert(i+j,c[x][i+j],d[x][i+j],1);

					z=nxt[z];

				}

				x=pre[x];

			}

		}

		else if(kind==2){

			int x=read(),y=nxt[x];

			nxt[x]=pre[y]=0;

			for(int i=1;i<50&&x;i++){

				int z=y;

				for(int j=1;i+j<=50&&z;j++){

					insert(i+j,c[x][i+j],d[x][i+j],-1);

					z=nxt[z];

				}

				x=pre[x];

			}

		}

		else{

			scanf("%s",s+1);int len=strlen(s+1),k=read();

			for(int i=1;i<=len;i++)a[i]=(1ll*a[i-1]*basec+s[i]-'0')%cmod;

			for(int i=1;i<=len;i++)b[i]=(1ll*b[i-1]*based+s[i]-'0')%dmod;

			int ans=1;

			for(int i=1;i<=len-k+1;i++){

				int x=cM(a[i+k-1]-1ll*a[i-1]*E[k]%cmod+cmod);

				int y=dM(b[i+k-1]-1ll*b[i-1]*f[k]%dmod+dmod);

				int num=0;

				for(int j=first[x];j;j=e[j].from)if(e[j].v==y&&e[j].k==k){num=e[j].x;break;}

				ans=1ll*ans*num%MOD;

			}

			printf("%d\n",ans);

		}

	}

	return 0;

}