题目传送门：P3823 [NOI2017] 蚯蚓排队
题意
操作一：使蚯蚓 \(j\) 及其所在队伍后面的所有蚯蚓全部排在蚯蚓 \(i\) 后，即蚯蚓 \(j\) 在队伍中的位置变为 \(i + 1\)，后面的以此类推。
操作二：使蚯蚓 \(i + 1\) 变为新的一队，即蚯蚓 \(i + 1\) 在队伍中的位置变为 \(1\)。
操作三：给定字符串 \(s\) 和一个整数 \(k\)，对于 \(s\) 每个长度为 \(k\) 的子串 \(s'\)，求所有字符串的所有子串中与 \(s'\) 相等的子串的数量。
思路
看完题，明显是哈希来求解，毕竟是哈希题单的题。此时注意数据范围，\(k \le 50\)。秉持着从小数据入手的原则，明显可以发现有可能可以暴力。
那么暴力的思路应该为：用一个链表维护子串的合并/断裂操作，使用哈希做查询操作。
由于每次的操作只会影响到 \(k\) 只蚯蚓的哈希值，所以每次更新的时间复杂度应为 \(O(k^2)\)。
鉴于 \(k\) 较小的数据，直接建一张关键字为哈希值的哈希表，使用哈希表查询即可。
代码
#include <bits/stdc++.h>
#define ull unsigned long long
using namespace std;
const int maxn = 2e5 + 5, q = 131, mod = 998244353, Hash_mod = 19260817, maxs = 1e7 + 5;
ull p[maxn], a[maxn], nxt[maxn], pre[maxn];
char str[maxs];
inline int read() {
int x = 0, f = 1;
char c;
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;
}
struct Hash_table {
ull head[Hash_mod], nxt[maxs], len[maxs], val[maxs], tot = 0, s[maxs];
void add(ull S, int l, int v) {
int tmp = S % Hash_mod;
for (int i = head[tmp]; i; i = nxt[i])
if (len[i] == l && s[i] == S) {
val[i] = (val[i] + v) % mod;
return ;
}
len[++tot] = l, val[tot] = v, s[tot] = S, nxt[tot] = head[tmp], head[tmp] = tot;
}
int query(ull S, int l) {
int tmp = S % Hash_mod ;
for (int i = head[tmp]; i; i = nxt[i])
if (len[i] == l && s[i] == S) return val[i];
return 0;
}
} Hash;
void link(int x, int y) {
nxt[x] = y, pre[y] = x;
ull pres = 0;
int tot = 0, len = 49;
for (int i = x; i && len; i = pre[i]) {
pres += a[i] * p[tot++] ;
ull s = pres, l = tot + 1;
for (int j = y; j && l <= 50; j = nxt[j], l++) {
s = s * q + a[j];
Hash.add(s, l, 1);
}
len--;
}
}
void cut(int x) {
int y = nxt[x], tot = 0, len = 49;
ull pres = 0;
for (int i = x; i && len; i = pre[i]) {
pres += a[i] * p[tot++];
ull s = pres, l = tot + 1;
for (int j = y; j && l <= 50; j = nxt[j], l++) {
s = s * q + a[j];
Hash.add(s, l, mod - 1);
}
len--;
}
nxt[x] = pre[y] = 0;
}
int query(int k) {
ull s = 0;
int len = strlen(str + 1), res = 1;
str[0] = '0';
for (int i = 1; i < k; i++)
s = s * q + str[i] - '0';
for (int i = k; i <= len; i++) {
s = s * q + str[i] - '0' - p[k] * (str[i - k] - '0');
res = 1ll * res * Hash.query(s, k) % mod;
}
return res;
}
int main() {
int n = read(), m = read();
for (int i = 1; i <= n; i++) {
a[i] = read();
Hash.add(a[i], 1, 1);
}
p[0] = 1;
for (int i = 1; i <= n; i++)
p[i] = p[i - 1] * q;
while (m--) {
int op = read();
if (op == 1) {
int x = read(), y = read();
link(x, y);
}
if (op == 2) {
int x = read();
cut(x);
}
if (op == 3) {
scanf("%s", str + 1);
int k = read();
printf("%d\n", query(k));
}
}
return 0;
}
注意：一定要用
usigned long long