题目描述 蚯蚓幼儿园有nnn只蚯蚓。幼儿园园长神刀手为了管理方便，时常让这些蚯蚓们列队表演。
所有蚯蚓用从 1 到 n 的连续正整数编号。每只蚯蚓的长度可以用一个正整数表示，根据入园要求，所有蚯蚓的长度都不超过 6 。神刀手希望这些蚯蚓排成若干个队伍，初始时，每只蚯蚓各自排成一个仅有一只蚯蚓的队伍，该蚯蚓既在队首，也在队尾。
神刀手将会依次进行 m 次操作，每个操作都是以下三种操作中的一种：
给出 i 和 j ，令 i 号蚯蚓与 j 号蚯蚓所在的两个队伍合并为一个队伍，具体来说，令 j 号蚯蚓紧挨在 i 号蚯蚓之后，其余蚯蚓保持队伍的前后关系不变。 给出 i ，令 i 号蚯蚓与紧挨其后的一只蚯蚓分离为两个队伍，具体来说，在分离之后， i 号蚯蚓在其中一个队伍的队尾，原本紧挨其后的那一只蚯蚓在另一个队伍的队首，其余蚯蚓保持队伍的前后关系不变。 给出一个正整数 k 和一个长度至少为 k 的数字串 s ，对于 s 的每个长度为 k 的连续子串 t （这样的子串共有 ∣s∣−k+1 个，其中 ∣s∣|s|∣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,…,n的蚯蚓的长度。
!!!
不想粘题了
好气
链接LOJ
题解
哈希能过
但要注意一下
每合并一次就相当于增加了50^2种情况
合并和拆分是一样的
然后查询的时候硬跑就可以了
#include <cstdio>
#include <cstring>
using namespace std;
#define LL unsigned long long
const int N = 300010, M = 15000010, L = 20000010;
const LL P = 23333333, p = 1000007, mod = 998244353;
int head[P], next[L], cnt[L], E, Next[N], Pre[N], a[N];
LL w[L], Pow[60];
int n, m;
char str[L];
void Insert(LL x, int y)
{
LL now = x % P;
bool flag = 0;
for (int i = head[now]; i; i = next[i])
if (w[i] == x)
{
cnt[i] += y;
flag = 1;
break;
}
if (!flag)
{
next[++E] = head[now];
head[now] = E;
cnt[E] = 1;
w[E] = x;
}
}
int Query(LL x)
{
LL now = x % P;
for (int i = head[now]; i; i = next[i])
if (w[i] == x)
return cnt[i];
return 0;
}
void Change(int x, int y)
{
int now = x;
for (int k = 1; k <= 50; k++)
{
int ret = now;
LL Hash = a[now];
for (int j = 1; j <= k; j++)
{
ret = Next[ret];
Hash = Hash * p + a[ret];
}
for (int l = k + 1; l <= 50; l++)
{
Insert(Hash, y);
ret = Next[ret];
if (!ret)
break;
Hash = Hash * p + a[ret];
}
now = Pre[now];
if (!now)
break;
}
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
{
scanf("%d", &a[i]);
Insert(a[i], 1);
}
Pow[0] = 1;
for (int i = 1; i <= 50; i++)
{
Pow[i] = Pow[i - 1] * p;
}
int op;
int x, y;
for (int i = 1; i <= m; i++)
{
scanf("%d", &op);
if (op == 1)
{
scanf("%d%d", &x, &y);
Next[x] = y;
Pre[y] = x;
Change(x, 1);
}
else if (op == 2)
{
scanf("%d", &x);
Change(x, -1);
Pre[Next[x]] = 0, Next[x] = 0;
}
else
{
scanf("%s", str + 1);
scanf("%d", &x);
LL ret = 0;
for (int i = 1; i <= x; i++)
ret = ret * p + str[i] - '0';
LL ans = Query(ret);
LL len = strlen(str + 1);
for (int i = x + 1; i <= len; i++)
{
ret = ret - (str[i - x] - '0') * Pow[x - 1];
ret = ret * p + (str[i] - '0');
ans = ans * Query(ret) % mod;
}
printf("%lld\n", ans);
}
}
}