「NOI2017」蚯蚓排队
观前提示
借鉴：洛谷题解区
做前知识：
1. 字符串哈希
2. 哈希表
题意：
Description
蚯蚓幼儿园有n只蚯蚓。幼儿园园长神刀手为了管理方便，时常让这些蚯蚓们列队表演。
所有蚯蚓用从 1 到 n 的连续正整数编号。每只蚯蚓的长度可以用一个正整数表示，根据入园要求，所有蚯蚓的长度都不超过 6 。神刀手希望这些蚯蚓排成若干个队伍，初始时，每只蚯蚓各自排成一个仅有一只蚯蚓的队伍，该蚯蚓既在队首，也在队尾。
神刀手将会依次进行 m 次操作，每个操作都是以下三种操作中的一种：
给出 i 和 j ，令 i 号蚯蚓与 j 号蚯蚓所在的两个队伍合并为一个队伍，具体来说，令 j 号蚯蚓紧挨在 i 号蚯蚓之后，其余蚯蚓保持队伍的前后关系不变。
给出 i ，令 i 号蚯蚓与紧挨其后的一只蚯蚓分离为两个队伍，具体来说，在分离之后， ii 号蚯蚓在其中一个队伍的队尾，原本紧挨其后的那一只蚯蚓在另一个队伍的队首，其余蚯蚓保持队伍的前后关系不变。
给出一个正整数 k 和一个长度至少为 k 的数字串 s ，对于 s 的每个长度为 k 的连续子串 tt （这样的子串共有 |s|-k+1 个，其中 |s| 为 s 的长度），定义函数 f(t) ，询问所有这些f(t)的乘积对 998244353 取模后的结果。其中f(t)的定义如下：
对于当前的蚯蚓队伍，定义某个蚯蚓的向后 kk 数字串为：从该蚯蚓出发，沿队伍的向后方向，寻找最近的 k 只蚯蚓（包括其自身），将这些蚯蚓的长度视作字符连接而成的数字串；如果这样找到的蚯蚓不足 k 只，则其没有向后kk数字串。例如蚯蚓的队伍为 10 号蚯蚓在队首，其后是 22 号蚯蚓，其后是 3 号蚯蚓（为队尾），这些蚯蚓的长度分别为 4 、 5 、 6 ，则 10 号蚯蚓的向后 3 数字串为456， 22 号蚯蚓没有向后 3 数字串，但其向后 2 数字串为56，其向后 1 数字串为5。
而 f(t) 表示所有蚯蚓中，向后 k 数字串恰好为 t 的蚯蚓只数。
Input Format
从标准输入读入数据。
输入文件的第一行有两个正整数 n,m ，分别表示蚯蚓的只数与操作次数。
第二行包含 n 个不超过 6 的正整数，依次表示编号为 n1,2,…,n 的蚯蚓的长度。
接下来 m 行，每行表示一个操作。每个操作的格式可以为：
1 i j（1≤i,j≤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) 的定义见题目描述。
同一行输入的相邻两个元素之间，用恰好一个空格隔开。
输入文件可能较大，请不要使用过于缓慢的读入方式。
Output Format
输出到标准输出。
依次对于每个形如3 s k的操作，输出一行，仅包含一个整数，表示询问的结果。
一句话题意：对一堆字符串进行合并，分离和查询
这时我们首先想到并查集。但是O（m + mn）的复杂度是不可接受的（28分，感谢lymsHz17的无私奉献）。
所以我们思考有什么更快的查询方法，在刷OI WIKI的时候，偶然发现了哈希链表，这不就是我们正在找的东西嘛！
极好的时间复杂度
但是问题来了：我不会写。
于是在借鉴题解充分学习后，有了以下代码，凑活看吧
tip 用了双哈希与哈希表，应该不用注释吧，其实是懒得打了
//「NOI2017」蚯蚓排队
#include<bits/stdc++.h>
#define ull unsigned long long
#define int long long
#define Blue_Archive return 0
#define rint register int
using namespace std;
const int N = 3e5 + 5;
const int K = 55;
const int P = 1e7 + 7;
const int P1 = 13;
const int P2 = 137;
const int mod = 998244353;char s[P];
int n,m,k;
int l[N];
int nxt[N];
int pre[N];
int bas1[K];
int hs1[K];
int hs2[K];
int hd[P];
int Nxt[N * K];
int Len[N * K];
int tot;
int cnt[N * K];
ull key[N * K];
ull bas2[K];
ull Hs1[K];
ull Hs2[K];inline void add(int L,int h1,ull h2,int v)
{for(int i = hd[h1];i;i = Nxt[i]){if(key[i] == h2 && Len[i] == L){cnt[i] += v;return;}}Len[++ tot] = L;key[tot] = h2;Nxt[tot] = hd[h1];hd[h1] = tot;cnt[tot] = 1;
}inline int query(int L,int h1,ull h2)
{for(int i = hd[h1];i;i = Nxt[i]){if(key[i] == h2 && Len[i] == L){return cnt[i];}}return 0;
}signed main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin >> n;cin >> m;for(int i = 1;i <= n;i ++){cin >> l[i];add(1,l[i],l[i],1);}for(int i = bas1[0] = bas2[0] = 1;i <= 51;i ++){bas1[i] = bas1[i-1] * P1 % P;bas2[i] = bas2[i-1] * P2;}for(int i = 1,op,x,y;i <= m;i ++){cin >> op;if(op == 1){cin >> x;cin >> y;int l1 = 0;int l2 = 0;for(int j = 1,t = x;j <= 50 && t;l1 ++,j ++,t = pre[t]){hs1[j] = (hs1[j - 1] + l[t] * bas1[j - 1]) % P;Hs1[j] = Hs1[j - 1] + l[t] * bas2[j - 1];}for(int j = 1,t = y;j <= 50 && t;l2 ++,j ++,t = nxt[t]){hs2[j] = (hs2[j - 1] * P1 + l[t]) % P;Hs2[j] = Hs2[j - 1] * P2 + l[t];}for(int l = 2;l <= 50 && l <= l1 + l2;l ++){for(int j = 1;j < l && j <= l1;j ++){if(l - j <= l2){add(l,(1ll * hs1[j] * bas1[l - j] + hs2[l - j]) % P,Hs1[j] * bas2[l - j] + Hs2[l - j],1);}}}nxt[x] = y;pre[y] = x;}if(op == 2){cin >> x;y = nxt[x];int l1 = 0;int l2 = 0;for(int j = 1,t = x;j <= 50 && t;l1 ++,j ++,t = pre[t]){hs1[j] = (hs1[j - 1] + l[t] * bas1[j - 1]) % P;Hs1[j] = Hs1[j - 1] + l[t] * bas2[j - 1];}for(int j = 1,t = y;j <= 50 && t;l2 ++,j ++,t = nxt[t]){hs2[j] = (hs2[j - 1] * P1 + l[t]) % P;Hs2[j] = Hs2[j - 1] * P2 + l[t];}for(int l = 2;l <= 50 && l <= l1 + l2;l ++){for(int j = 1;j < l && j <= l1;j ++){if(l - j <= l2){add(l,(1ll * hs1[j] * bas1[l - j] + hs2[l - j]) % P,Hs1[j] * bas2[l - j] + Hs2[l - j],-1);}}}nxt[x] = 0;pre[y] = 0;}if(op == 3){cin >> (s + 1);cin >> k;int ans = 1;int h1 = 0;int len = strlen(s + 1);ull h2 = 0;for(int i = 1;i <= k;i ++){h1 = (h1 * P1 + s[i] - '0') % P;h2 = h2 * P2 + s[i] - '0';}for(int i = k;i <= len;i ++){ans = 1ll * ans * query(k,h1,h2) % mod;if(ans == 0) break;h1 = ((h1 - 1ll * (s[i - k + 1] - '0') * bas1[k - 1] % P + P) * P1 + (s[i + 1] - '0')) % P;h2 = (h2 - (s[i - k + 1] - '0') * bas2[k - 1]) * P2 + s[i + 1] - '0';}cout << ans << "\n";}}Blue_Archive;
}
/////////////////////////////
// Shiroko //
/////////////////////////////