蚯蚓排队
题目描述
蚯蚓幼儿园有\(n\)只蚯蚓。幼儿园园长神刀手为了管理方便，时常让这些蚯蚓们列队表演。
所有蚯蚓用从\(1\)到\(n\)的连续正整数编号。每只蚯蚓的长度可以用一个正整数表示，根据入园要求，所有蚯蚓的长度都不超过\(6\)。神刀手希望这些蚯蚓排成若干个队伍，初始时，每只蚯蚓各自排成一个仅有一只蚯蚓的队伍，该蚯蚓既在队首，也在队尾。
神刀手将会依次进行\(m\)次操作，每个操作都是以下三种操作中的一种：
-
给出\(i\)和\(j\)，令\(i\)号蚯蚓与\(j\)号蚯蚓所在的两个队伍合并为一个队伍，具体来说，令\(j\)号蚯蚓紧挨在\(i\)号蚯蚓之后，其余蚯蚓保持队伍的前后关系不变。
-
给出\(i\)，令\(i\)号蚯蚓与紧挨其后的一只蚯蚓分离为两个队伍，具体来说，在分离之后，\(i\)号蚯蚓在其中一个队伍的队尾，原本紧挨其后的那一只蚯蚓在另一个队伍的队首，其余蚯蚓保持队伍的前后关系不变。
-
给出一个正整数\(k\)和一个长度至少为\(k\)的数字串\(s\)，对于\(s\)的每个长度为\(k\)的连续子串\(t\) （这样的子串共有$\left| s\right|-k+1 $ 个，其中\(\left| s\right|\) 为\(s\)的长度），定义函数\(f(t)\) ，询问所有这些的乘积对\(998244353\) 取模后的结果。其中 \(f(t)\) 的定义如下：
对于当前的蚯蚓队伍，定义某个蚯蚓的向后\(k\)数字串为：从该蚯蚓出发，沿队伍的向后方向，寻找最近的\(k\)只蚯蚓（包括其自身），将这些蚯蚓的长度视作字符连接而成的数字串；如果这样找到的蚯蚓不足\(k\)只，则其没有向后数字串。而 \(f(t)\) 表示所有蚯蚓中，向后\(k\)数字串恰好为\(t\)的蚯蚓只数。
输入格式
输入文件的第一行有两个正整数\(n\)，\(m\)，分别表示蚯蚓的只数与操作次数。
第二行包含\(n\)个不超过\(6\)的正整数，依次表示编号为$ 1,2,3,\dots,n $的蚯蚓的长度。
接下来\(m\)行，每行表示一个操作。每个操作的格式可以为：
-
$ 1\ i\ j $（$1\le i,j\le 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)\) 的定义见题目描述。
同一行输入的相邻两个元素之间，用恰好一个空格隔开。
输入文件可能较大，请不要使用过于缓慢的读入方式。
输出格式
输出到标准输出。
依次对于每个形如 \(3\ s\ k\) 的操作，输出一行，仅包含一个整数，表示询问的结果。
数据范围与提示
保证 $ n\le 2\times 10^5 $， $ m\le 5\times 10^5 $ ，\(k\le 50\)。
设 $ \sum \left| s\right| $ 为某个输入文件中所有询问的\(s\) 的长度总和，则 $ \sum \left| s\right| \le 10^7 $。
设 \(c\) 为某个输入文件中形如$ 2\ i$ 的操作的次数，则 $ c\le 10^3 $ 。
题解
自我感觉这题够恶心的，题面很长还难理解，大概是说给出\(n\)个长度为\(1\)的字符串，支持三种操作：合并两个字符串，拆分一个字符串，给定一个长度至少为\(k\)的字符串\(s\)，将其所有长为\(k\)的子串取出，对于每个子串，\(f(t)\)为在蚯蚓组成的字符串中相等的个数。求 $ \prod f(t) $ 。
一眼就不很会，wzh先生直接投降看题解了，要用哈希表，然后我也去学哈希表，再来做题。
不得不说，这数据出的太绝了。直接想法：
对于操作\(3\)，当然是枚举s的子串计算\(hash\)，再利用哈希表计算\(f(t)\)，总复杂度 \(O(\left| s\right|)\),可行，但需要预知现有的每个蚯蚓字符串的状态(hash)。
对于操作\(1,2\)，我们很明显需要统计新出现的字符串的\(hash\)，放入哈希表，以便操作\(3\)，但这样单次复杂度貌似是\(O(n^2)\)。
然后就不知道怎么办了。
感谢wzh先生的提示
你看这个K它多可爱啊
你看这个c它多可爱啊
思考，思考......悟了！
当合并两个字符串时，由于保证 \(K\le 50\)，所以长度超过50的子串是无用的，因此每次合并，只需预处理长度不超过\(50\)的字符串的哈希值，利用链表保存每只蚯蚓的前驱和后继，每次操作 \(O(K^2)\)。
这样看来，最坏复杂的 \(O(mK^2)\)，好像还是不能过。
而 \(c\le 1000\) ，复杂度 \(O(cK^2)\)，可以忽略不计。这样字符串合并后可以看作不会再拆开，子串的长度只有 \(nK\)个，复杂度\(O(nK)\)。
总复杂度 \(O(nk+ck^2+\left| s\right|)\)
Code
#include<bits/stdc++.h>
using namespace std;
#define int unsigned long long
const int N=1e6;
const int mod=998244353;
const int M=1e7+19;
const int base=233;
const int K=50;
int n,m,a,b,k,l[N],t;
int h[N],p[N];
int cnt,head[N*50],nxt[N*50],num[N*50],sum[N*50],to[N],fo[N];
char s[N*10+14];
void insert(int key)
{
int hash=key%M;
for(int i=head[hash];i;i=nxt[i]){
if(num[i]==key){
sum[i]++;
return ;
}
}
cnt++;
sum[cnt]=1;
nxt[cnt]=head[hash];
head[hash]=cnt;
num[cnt]=key;
}
void cutoff(int key)
{
int hash=key%M;
for(int i=head[hash];i;i=nxt[i]){
if(num[i]==key){
sum[i]--;
return ;
}
}
}
int query(int key)
{
int hash=key%M;
for(int i=head[hash];i;i=nxt[i]){
if(num[i]==key){
return sum[i];
}
}
return 0;
}
inline int read()
{
int f=1,w=0;
char c=getchar();
while(c>'9'||c<'0'){
c=getchar();
}
while(c<='9'&&c>='0'){
w=w*10+(c-'0');
c=getchar();
}
return w*f;
}
void write1(int x){
if(x>9) write1(x/10);
putchar(x%10+48);
}
inline void write(int x){
write1(x);
}
signed main()
{
n=read();
m=read();
p[0]=1;
for(int i=1;i<=K;i++){
p[i]=(p[i-1]*base);
}
for(int i=1;i<=n;i++){
l[i]=read();
fo[i]=i;
to[i]=i;
insert((l[i]+'0'));
}
while(m--){
t=read();
if(t==1){
a=read();b=read();
int x=a,w=b,z,y;
int hx=0,hy=0;
for(int i=1;i<K;i++){
if(fo[x]==x)break;
x=fo[x];
}
for(int i=1;i<K;i++){
if(to[w]==w)break;
w=to[w];
}
z=a;
for(int i=1;;i++){
y=b;
hx=(l[z]+'0')*p[i-1]+hx;
hy=0;
for(int j=1;;j++){
hy=hy*base+(l[y]+'0');
insert(hx*p[j]+hy);
if(y==w||j+i>=K)break;
y=to[y];
}
if(z==x)break;
z=fo[z];
}
fo[b]=a;
to[a]=b;
}
else if(t==2){
a=read();
b=to[a];
int x=a,w=b,z,y;
int hx=0,hy=0;
for(int i=1;i<K;i++){
if(fo[x]==x)break;
x=fo[x];
}
for(int i=1;i<K;i++){
if(to[w]==w)break;
w=to[w];
}
z=a;
for(int i=1;;i++){
y=b;
hx=hx+(l[z]+'0')*p[i-1];
hy=0;
for(int j=1;;j++){
hy=hy*base+(l[y]+'0');
cutoff((hx*p[j])+hy);
if(y==w||j+i>=K)break;
y=to[y];
}
if(z==x)break;
z=fo[z];
}
fo[b]=b;
to[a]=a;
}
else{
scanf("%s",s);
k=read();
int shadow=0,ans=1,i;
bool flag=0;
for(i=0;i+1<k;i++){
shadow=(shadow*base+s[i]);
}
int len=strlen(s);
for(i=0;i+k-1<len;i++){
flag=1;
if(i==0){
shadow=(shadow*base+s[i+k-1]);
ans*=query(shadow);
ans%=mod;
}
else{
shadow=shadow*base-s[i-1]*p[k]+s[i+k-1];
ans*=query(shadow);
ans%=mod;
}
}
if(!flag)ans=0;
write(ans);puts(" ");
}
}
}
后续
题还是比较难想的，调了一下午后还是\(TLE\ 88pts\)，最后不得不先放下了，集训最后一天又拿出来，\(hangry\)和\(CuFeO4\)帮我卡常，但越卡越T，甚至WA了，最后想起来哈希表取模用的\(M=1e6+19\)，太小了，这样哈希冲突的概率更大，链表的长度更大，所以查询，修改速度慢了，暴力改为\(1e7+19\)，AC
标签：le,hash,int,题解,排队,队伍,长度,蚯蚓 From： https://www.cnblogs.com/abnormal123/p/18009842