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

所有蚯蚓用从 $1$ 到 $n$ 的连续正整数编号。每只蚯蚓的长度可以用一个 $1 \sim 6$ 的正整数表示，scx 希望这些蚯蚓排成若干个队伍，初始时，每只蚯蚓各自排成一个仅有一只蚯蚓的队伍，该蚯蚓既在队首，也在队尾。

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

对于当前的蚯蚓队伍，定义某个蚯蚓的向后 $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$ ($1 \leq n \leq 2 \times 10^5, 1 \leq m \leq 3 \times 10^5$)，分别表示蚯蚓的只数与操作次数。

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

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

输出格式

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

题解

注意到 $k \leq 50$ 这个条件，可以发现，只需要存储长度不超过 $50$ 的子串。

考虑使(shou)用(xie) hash_map，记录每种 (长度不超过 $k$ 的) 子串的出现次数。

每一次合并 (分裂)，可以看出至多增加 (减少) $O(k^2)$ 个新的字符串，因此可以直接枚举 $i$ 所在的链表尾和 $j$ 所在的链表头将增加的长度不超过 $k$ 的字符串放入 hash_map 中。

其实这两个操作可以统一放入一个函数 modify(x, y, op) 中，用 op 控制合并 (增加字符串) 还是分裂 (减少字符串)。

最后统计的时候，枚举 $s$ 的所有长度为 $k$ 的子串，分别在 hash_map 中查值对应相乘即可，~~算法难度其实也不是很大~~。

代码

#include <bits/stdc++.h>
#define N 512202
#define S 10073306
#define K 50
#define ID isdigit(c = *next++)
#define RT if(c < 0) return flag = 0, *this
using namespace std;

struct Istream{
    int flag; char *next, buf[80000000];
    void init(FILE *f = stdin){fread(buf, 1, sizeof buf, f); next = buf;}
    Istream& operator >> (int &x){
        int c, l = 0; x = 0;
        for(; !ID; l = c) RT;
        for(x = c - 48; ID; x = x * 10 + (c - 48)) RT; RT;
        if(l == 45) x = -x;
        return flag = 1, *this;
    }
    Istream& operator >> (char *x){
        int c;
        for(; (c = *next++) <= ' '; ) RT;
        for(*x++ = c; (c = *next++) > ' '; *x++ = c) RT; RT;
        *x = '\0';
        return flag = 1, *this;
    }
    char get(){return *next++;}
    operator void *() {return flag ? this : 0;}
}Cin;

struct Ostream{
    FILE *_f; char buf[34];
    void init(FILE *f = stdout){_f = f;}
    Ostream& operator << (long long x){
        if(!x) return put(48), *this;
        if(x < 0){put(45); x = -x;}
        int i;
        for(i = 0; x > 0; x /= 10) buf[i++] = x % 10 + 48;
        while(--i >= 0) put(buf[i]);
        return *this;
    }
    Ostream& operator << (char c){return put(c), *this;}
    void put(char c){fputc(c, _f);}
}Cout;

typedef long long ll;
const ll MOD = 998244353, HASH_MAX = 16777215;
const ll mod0 = 998244353, mod1 = 1000000007;

struct data{
    int h1, h2;
    data (int Hash = 0): h1(Hash), h2(Hash) {}
    data (int H1, int H2): h1(H1), h2(H2) {}
    bool operator == (const data &b) {return h1 == b.h1 && h2 == b.h2;}
    data operator + (const data &b) {return data((h1 + b.h1) % mod0, (h2 + b.h2) % mod1);}
    data operator - (const data &b) {return data((h1 - b.h1 + mod0) % mod0, (h2 - b.h2 + mod1) % mod1);}
    data operator << (int b);
    inline int getHash() {return ((ll)h1 * 85367 + h2) & HASH_MAX;}
};
data pw[57];

data data::operator << (int b){return data((ll)h1 * pw[b].h1 % mod0, (ll)h2 * pw[b].h2 % mod1);}

int cnt, first[HASH_MAX + 2], nxt[HASH_MAX + 2], val[HASH_MAX + 2]; data z[HASH_MAX + 2];

void add(data h, int v) {
    int x = h.getHash(), i;
    for(i = first[x]; i; i = nxt[i]) if(z[i] == h) return val[i] += v, void(0);
    z[++cnt] = h; val[cnt] = v; nxt[cnt] = first[x]; first[x] = cnt;
}

int count(data h){
    int x = h.getHash(), i;
    for(i = first[x]; i; i = nxt[i]) if(z[i] == h) return val[i];
    return 0;
}

int n, q, c;
int a[N], next[N], last[N];
int stk1[57], stk2[57], cnt1, cnt2;
char s[S];
data ha[S];

void modify(int x, int y, int op){
    int i, j; data d(0), t;
    cnt1 = cnt2 = 0;
    for(i = x; i && cnt1 < K; i = last[i]) stk1[cnt1++] = a[i];
    for(j = y; j && cnt2 < K; j = next[j]) stk2[cnt2++] = a[j];
    stk1[cnt1] = 0;
    for(i = cnt1 - 1; ~i; --i) d = (d << 1) + data(stk1[i]);
    for(i = cnt1; i; --i){
        t = d - (data(stk1[i]) << i); d = t;
        for(j = 0; j < cnt2 && i + j <= K; ++j){
            t = (t << 1) + data(stk2[j]);
            add(t, op);
        }
    }
}

void solve(int k){
    int len = 0, i, j; ll ans = 1;
    for(char *p = s; *p; ++p, ++len) ha[len + 1] = (ha[len] << 1) + data(*p &= 15);
    for(i = 0; i + k <= len; ++i){
        j = count(ha[i + k] - (ha[i] << k));
        (ans *= j) %= MOD; if(!ans) break;
    }
    Cout << ans << '\n';
}

int main(){
    int i, j;
    pw[0] = data(1);
    for(i = 1; i < 57; ++i) pw[i] = data((ll)pw[i - 1].h1 * 4621 % mod0, (ll)pw[i - 1].h2 * 6577 % mod1);
    Cin.init(); Cout.init(); Cin >> n >> q;
    for(i = 1; i <= n; ++i) {Cin >> a[i]; add(data(a[i]), 1);}
    for(; q; --q)
        switch(Cin >> c, c){
            case 1:
                Cin >> i >> j;
                next[i] = j; last[j] = i;
                modify(i, j, 1);
                break;
            case 2:
                Cin >> i; j = next[i];
                next[i] = last[j] = 0;
                modify(i, j, -1);
                break;
            case 3:
                Cin >> s >> i;
                solve(i);
                break;
        }
    return 0;
}

坑

坑1：由于长度不超过 $k$ 的子串个数有 $\Theta(6^k)$ 个，最坏情况下约有 $9.7 \times 10^{38}$ 个，~~因此需要 $17$ 个字节来存储~~，所以要考虑写一个双 Hash (单 Hash 很有可能被卡 WA，三 Hash 要 TLE) 来代表这个字符串 (尽量使用经典的可逆的多项式 Hash)，再放进 hash_map 中。

另外模数要选好，尽量选择形如 $2^n - 1$ 的梅森数，可以用 & 运算，从而避免大量的 % 运算。

坑2：这道题都说过要 IO 优化了，所以肯定要写的，而且这道题的卡常还是非常厉害的，尽量不要用 class 或 struct，可以用 namespace 或者干脆直接拿出来，减少不必要的常数。

题目描述

输入格式

输出格式

题解

代码

坑