「LOJ 2303」「NOI2017」蚯蚓排队

发表于

蚯蚓幼儿园有 nn 只蚯蚓。幼儿园园长神刀手为了管理方便，时常让这些蚯蚓们列队表演。

所有蚯蚓用从 11 到 nn 的连续正整数编号。每只蚯蚓的长度可以用一个正整数表示，根据入园要求，所有蚯蚓的长度都不超过 66 。神刀手希望这些蚯蚓排成若干个队伍，初始时，每只蚯蚓各自排成一个仅有一只蚯蚓的队伍，该蚯蚓既在队首，也在队尾。

神刀手将会依次进行 mm 次操作，每个操作都是以下三种操作中的一种：

  • 给出 ii 和 jj ，令 ii 号蚯蚓与 jj 号蚯蚓所在的两个队伍合并为一个队伍，具体来说，令 jj 号蚯蚓紧挨在 ii 号蚯蚓之后，其余蚯蚓保持队伍的前后关系不变。
  • 给出 ii ，令 ii 号蚯蚓与紧挨其后的一只蚯蚓分离为两个队伍，具体来说，在分离之后， ii 号蚯蚓在其中一个队伍的队尾，原本紧挨其后的那一只蚯蚓在另一个队伍的队首，其余蚯蚓保持队伍的前后关系不变。
  • 给出一个正整数 kk 和一个长度至少为 kk 的数字串 ss ，对于 ss 的每个长度为 kk 的连续子串 tt （这样的子串共有 ∣s∣−k+1|s|-k+1 个，其中 ∣s∣|s| 为 ss 的长度），定义函数 f(t)f(t) ，询问所有这些 f(t)f(t) 的乘积对 998244353998244353 取模后的结果。其中 f(t)f(t) 的定义如下：

对于当前的蚯蚓队伍，定义某个蚯蚓的向后 kk 数字串为：从该蚯蚓出发，沿队伍的向后方向，寻找最近的 kk 只蚯蚓（包括其自身），将这些蚯蚓的长度视作字符连接而成的数字串；如果这样找到的蚯蚓不足 kk 只，则其没有向后 kk 数字串。

而 f(t)f(t) 表示所有蚯蚓中，向后 kk 数字串恰好为 tt 的蚯蚓只数。

Constraints

n≤2×105n \leq 2 \times 10^{5} ， m≤5×105m \leq 5 \times 10^{5} ， k≤50k \leq 50 ， ∑∣s∣≤107\sum |s| \leq 10^{7}

Solution

暴力维护对每个队伍链表，维护每条蚯蚓向后长度为 kk 的字符串的哈希值。

每一次修改操作只需要暴力修改跨越操作点的 k2k^2 个字符串，查询时直接枚举。

从总体考虑合并操作，可得时间复杂度实际为 O(ck2+nk+∑∣s∣)O(ck^2+nk+\sum |s|) 。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include<cstdio>
#include<algorithm> 
#include<cstring>
#define LL long long
using namespace std;
const int N=2e5+5;
const int L=1e7+5;
const int K=55;
const int sbas=233;
const int bbas=173;
const int smod=3715417;
const int bmod=1e9+7;
const int mod=998244353;
int n,m,cnt,ans,num,first[smod+5];
int op,x,y,z,leng,nxt[N],lst[N];
int a[N],S[K],B[K],s[N][K],b[N][K];
int SS,BB,ss[L],bb[L];
char ch[L];
struct edge{int to,next,k,c;}e[N*K];
int read()
{
	int x=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
	return x*f;
}
void Mod(int& a,int b){a+=b;if(a>=mod)a-=mod;}
void ins(int small,int big,int len,int val)
{
	for(int i=first[small];i;i=e[i].next)
		if(e[i].to==big&&e[i].k==len){Mod(e[i].c,val);return;}
	e[++cnt]=(edge){big,first[small],len,val};first[small]=cnt;
}
int main()
{
	n=read();m=read();
	S[0]=1;for(int i=1;i<=50;i++)S[i]=1ll*S[i-1]*sbas%smod;
	B[0]=1;for(int i=1;i<=50;i++)B[i]=1ll*B[i-1]*bbas%bmod;
	for(int i=1;i<=n;i++)
	{
		a[i]=read();
		s[i][1]=b[i][1]=a[i];
		ins(a[i],a[i],1,1);
	}
	while(m--)
	{
		op=read();
		if(op==1)
		{
			x=read();y=read();nxt[x]=y;lst[y]=x;
			for(int i=1;i<50&&x;i++)
			{
				z=y;
				for(int j=1;i+j<=50&&z;j++)
				{
					s[x][i+j]=(1ll*s[x][i+j-1]*sbas+a[z])%smod;
					b[x][i+j]=(1ll*b[x][i+j-1]*bbas+a[z])%bmod;
					ins(s[x][i+j],b[x][i+j],i+j,1);z=nxt[z];
				}
				x=lst[x];
			}
		}
		else if(op==2)
		{
			x=read();y=nxt[x];nxt[x]=lst[y]=0;
			for(int i=1;i<50&&x;i++)
			{
				z=y;
				for(int j=1;i+j<=50&&z;j++)
					ins(s[x][i+j],b[x][i+j],i+j,-1),z=nxt[z];
				x=lst[x];
			}
		}
		else
		{
			scanf("%s",ch+1);leng=strlen(ch+1);
			x=read();ans=1;
			for(int i=1;i<=leng;i++)
			{
				ss[i]=(1ll*ss[i-1]*sbas+ch[i]-'0')%smod;
				bb[i]=(1ll*bb[i-1]*bbas+ch[i]-'0')%bmod;
			}
			for(int i=1;i<=leng-x+1;i++)
			{
				SS=(ss[i+x-1]-1ll*ss[i-1]*S[x]%smod+smod)%smod;
				BB=(bb[i+x-1]-1ll*bb[i-1]*B[x]%bmod+bmod)%bmod;
				num=0;
				for(int i=first[SS];i;i=e[i].next)
					if(e[i].to==BB&&e[i].k==x){num=e[i].c;break;}
				ans=1ll*ans*num%mod;
			}
			printf("%d\n",ans);
		}
	}
	return 0;
}