「NOI2017」蚯蚓排队

发表于
字数统计: 2,111字 | 阅读时长 ≈ 10min

「NOI2017」蚯蚓排队

题目描述

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

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

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

  1. 给出 $i$ 和 $j$ ，令 $i$ 号蚯蚓与 $j$ 号蚯蚓所在的两个队伍合并为一个队伍，具体来说，令 $j$ 号蚯蚓紧挨在 $i$ 号蚯蚓之后，其余蚯蚓保持队伍的前后关系不变。

  2. 给出 $i$ ，令 $i$ 号蚯蚓与紧挨其后的一只蚯蚓分离为两个队伍，具体来说，在分离之后， $i$ 号蚯蚓在其中一个队伍的队尾，原本紧挨其后的那一只蚯蚓在另一个队伍的队首，其余蚯蚓保持队伍的前后关系不变。

  3. 给出一个正整数 $k$ 和一个长度至少为 $k$ 的数字串 $s$ ，对于 $s$ 的每个长度为 $k$ 的连续子串 $t$ （这样的子串共有 $|s|-k+1$ 个，其中 $|s|$ 为 $s$ 的长度），定义函数 $f(t)$ ，询问所有这些$f(t)$的乘积对 $998244353$ 取模后的结果。其中$f(t)$的定义如下：

对于当前的蚯蚓队伍，定义某个蚯蚓的向后 $k$ 数字串为：从该蚯蚓出发，沿队伍的向后方向，寻找最近的 $k$ 只蚯蚓（包括其自身），将这些蚯蚓的长度视作字符连接而成的数字串；如果这样找到的蚯蚓不足 $k$ 只，则其没有向后$k$数字串。例如蚯蚓的队伍为 $10$ 号蚯蚓在队首，其后是 $22$ 号蚯蚓，其后是 $3$ 号蚯蚓（为队尾），这些蚯蚓的长度分别为 $4$ 、 $5$ 、 $6$ ，则 $10$ 号蚯蚓的向后 $3$ 数字串为456， $22$ 号蚯蚓没有向后 $3$ 数字串，但其向后 $2$ 数字串为56，其向后 $1$ 数字串为5。

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

输入格式

从标准输入读入数据。

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

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

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

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

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

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

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

输入文件可能较大，请不要使用过于缓慢的读入方式。

输出格式

输出到标准输出。

依次对于每个形如3 $s$ $k$的操作，输出一行，仅包含一个整数，表示询问的结果。

数据范围与提示

保证 $n \leq 2 \times 10^{5}$，$m \leq 5 \times 10^{5}$，$k \leq 50$ 。

设 $\sum |s|$ 为某个输入文件中所有询问的 $s$ 的长度总和，则 $\sum |s| \leq 10^{7}$ 。

设 $c$ 为某个输入文件中形如2 $i$的操作的次数，则 $c \leq 10^{3}$ 。

每个测试点的详细信息见下表：

测试点编号 $n$ $m$ $k$ $\sum |s|$ $c$ 全为$\texttt{1}$
1 $=1$ $\leq 10^{3}$ $=1$ $\leq 10^{3}$ $=0$ No
2 $\leq 20$ $\leq 40$ $\leq 10$
3 $\leq 150$ $\leq 2,000$ $\leq 50$ $\leq 10^{3}$
4 $\leq 500$ $\leq 600$ $=0$
5 $\leq 10^{3}$ $\leq 2,000$ $\leq 10^{3}$
6 $\leq 5 \times 10^{4}$ $\leq 6 \times 10^{4}$ $\leq 5$ $\leq 5 \times 10^{4}$
7 $\leq 50$ $=0$ Yes
8 No
9 $\leq 10^{3}$
10 $\leq 8 \times 10^{4}$ $\leq 2.5 \times 10^{6}$ $=0$
11 $\leq 10^{3}$
12 $\leq 10^{5}$ $\leq 1.1 \times 10^{5}$ $\leq 6$ $\leq 10^{5}$
13 $\leq 50$ $=0$ Yes
14 No
15 $\leq 10^{3}$
16 $\leq 1.5 \times 10^{5}$ $\leq 5 \times 10^{6}$ $=0$
17 $\leq 10^{3}$
18 $\leq 2 \times 10^{5}$ $\leq 5 \times 10^{5}$ $=1$ $\leq 10^{7}$ $=0$
19 $\leq 10^{3}$
20 $\leq 2.5 \times 10^{5}$ $\leq 7$ $\leq 2 \times 10^{5}$
21 $\leq 50$ $=0$ Yes
22 No
23 $\leq 10^{3}$
24 $\leq 3 \times 10^{5}$ $\leq 10^{7}$ $=0$
25 $\leq 10^{3}$

如果一个测试点的“全为1”的一列为“Yes”，表示该测试点的所有蚯蚓的长度均为1，并且所有询问串$s$的每一位也均为1。

一开始竟然没有注意到所有的$K\leq50$所以卡了好久……

题目显然要求与$\sum|s|$相关的算法，而每次询问似乎无法避免地要讨论所有的子串$t$。每次想要知道某个字符串出现的次数，要求$O(1)$处理字符串的变化。那么考虑Hash，将以每个位置作为结尾的长度为$1,2,3,…,K$的子串的Hash值都记录下来。为了知道出现次数采用Hash表以实现近似$O(1)$的复杂度。由于本题的空间给得很大，Hash表也可以开得很大。

对于拆分和合并操作暴力更新，看起来好像每次最坏是$O(K^2)$的，但是好像有势能分析证明达不到这么多？反正能过就是了。

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
97
98
99
100
101
102
103
104
105
#include<stdio.h>
#include<algorithm>
#include<cstring>
#define MAXN 200005
#define ull unsigned long long
#define LL long long
using namespace std;
const ull sd=1234321237;
const LL mod=998244353;

struct Hash_Table{
const static int MOD=10000007;
#define TOT 20000000
ull state[TOT];int val[TOT];
int las[MOD],nex[TOT],tot;

int& operator[](ull st){
	ull p=st%MOD;int i;
	for(i=las[p];i;i=nex[i])if(state[i]==st)return val[i];
	nex[++tot]=las[p];
	las[p]=tot;
	state[tot]=st;
	return val[tot];
}

}M;

int N,Q,A[MAXN],nexp[MAXN],lasp[MAXN];
char s[MAXN];int K,len;
ull pw[55];

void Merge(int x,int y){
	int i,j,k,l;ull hs;
	
	for(i=y,k=1;i&&k<=50;i=nexp[i],k++){
		hs=0;
		for(j=i,l=1;j&&l<=50;j=lasp[j],l++){
			hs=hs+A[j]*pw[l-1];
			M[hs]--;
		}
	}
	nexp[x]=y;lasp[y]=x;
	for(i=y,k=1;i&&k<=50;i=nexp[i],k++){
		hs=0;
		for(j=i,l=1;j&&l<=50;j=lasp[j],l++){
			hs=hs+A[j]*pw[l-1];
			M[hs]++;
		}
	}
}

void Split(int x){
	int i,j,k,l,y=nexp[x];ull hs;
	
	for(i=y,k=1;i&&k<=50;i=nexp[i],k++){
		hs=0;
		for(j=i,l=1;j&&l<=50;j=lasp[j],l++){
			hs=hs+A[j]*pw[l-1];
			M[hs]--;
		}
	}
	nexp[x]=0;lasp[y]=0;
	for(i=y,k=1;i&&k<=50;i=nexp[i],k++){
		hs=0;
		for(j=i,l=1;j&&l<=50;j=lasp[j],l++){
			hs=hs+A[j]*pw[l-1];
			M[hs]++;
		}
	}
}

void GetAns(){
	LL ret=1;ull hs=0;int i;
	for(i=1;i<=K;i++)hs+=pw[K-i]*(s[i]-'0');
	ret=(LL)ret*M[hs]%mod;
	for(;i<=len;i++){
		hs=(hs-pw[K-1]*(s[i-K]-'0'))*sd+s[i]-'0';
		ret=(LL)ret*M[hs]%mod;
	}
	printf("%lld\n",ret);
}

int main(){
	int i,x,y,ty;
	scanf("%d%d",&N,&Q);
	for(i=1;i<=N;i++)scanf("%d",&A[i]),M[A[i]]++;//nexp[i]=lasp[i]=i;
	for(pw[0]=1,i=1;i<=50;i++)pw[i]=pw[i-1]*sd;
	
	for(i=1;i<=Q;i++){
		scanf("%d",&ty);
		if(ty==1){
			scanf("%d%d",&x,&y);
			Merge(x,y);
		}
		else if(ty==2){
			scanf("%d",&x);
			Split(x);
		}
		else{
			scanf("%s%d",s+1,&K);
			len=strlen(s+1);
			GetAns();
		}
	}
}