给出 $n$ 个字符，初始每个字符单独成字符串。支持 $m$ 次操作，每次为一下三种之一：
- $1\ i\ j$ ：将以 $i$ 结尾的串和以 $j$ 开头的串连到一起。
- $2\ i$ ：将 $i$ 所在串从 $i$ 位置和 $i$ 下一个位置之间断开。
- $3\ S\ k$ ：对于字符串 $S$ 每个长度为 $k$ 的子串，统计它在这 $n$ 个字符组成所有字符串中出现的次数，求所有统计结果的乘积模 $998244353$ 的结果。
$n\le 2\times 10^5$ ，$m\e5\times 10^5$ ，$\sum|S|\le 10^7$ ，$k\le 50$ ，$2$ 操作次数不超过 $1000$ ，字符集大小为 $'1'\sim '6'$ 。
题解
Hash
一个显而易见的做法是：维护所有这 $n$ 个字符组成的长度在 $1\sim 50$ 之间的字符串的Hash值，查询时直接统计Hash值出现次数即可。
这样做的时间复杂度是什么呢？
看起来有 $m$ 次合并，是 $mk^2$ 的。
实则不然，当没有 $2$ 操作时，最终得到的只有 $nk$ 个子串，因此上界严格时复杂度就是 $O(nk)$ 的。而 $2$ 操作只有 $1000$ 次，每次会产生 $k^2$ 的势能贡献，这一部分也只有 $O(ck^2)$ 。
使用自然溢出Hash (范围是 $2^{64}=1.8\times 10^{19}$ ) ，再映射到大小为 $10233333$ 的哈希表上即可通过。
时间复杂度 $O(nk+ck^2+\sum|S|)$ 。
考场上想出正解，结果由于使用map只得到52分...
#include#include #include using namespace std;typedef unsigned long long ull;struct hashmap{ int head[10233333] , len[20000010] , cnt[20000010] , next[20000010] , tot; ull val[20000010]; inline void insert(int l , ull v) { int x = v % 10233333 , i , last = 0; for(i = head[x] ; i ; last = i , i = next[i]) if(len[i] == l && val[i] == v) break; if(i) cnt[i] ++ ; else { if(!last) head[x] = ++tot; else next[last] = ++tot; len[tot] = l , val[tot] = v , cnt[tot] ++ ; } } inline void erase(int l , ull v) { int x = v % 10233333 , i; for(i = head[x] ; i ; i = next[i]) if(len[i] == l && val[i] == v) cnt[i] -- ; } inline int find(int l , ull v) { int x = v % 10233333 , i; for(i = head[x] ; i ; i = next[i]) if(len[i] == l && val[i] == v) return cnt[i]; return 0; }}mp;int a[200010] , last[200010] , next[200010];ull base[55];char str[10000010];int main(){ int n , m , i , j , p , q , opt , x , y; ull vx , vy , ans; scanf("%d%d" , &n , &m); base[0] = 1; for(i = 1 ; i < 50 ; i ++ ) base[i] = base[i - 1] * 233; for(i = 1 ; i <= n ; i ++ ) scanf("%d" , &a[i]) , mp.insert(1 , a[i] ^ '0'); while(m -- ) { scanf("%d" , &opt); if(opt == 1) { scanf("%d%d" , &x , &y) , next[x] = y , last[y] = x , vx = 0; for(i = 1 , p = x ; i < 50 && p ; i ++ , p = last[p]) { vx += (a[p] ^ '0') * base[i - 1] , vy = 0; for(j = 1 , q = y ; i + j <= 50 && q ; j ++ , q = next[q]) vy = vy * 233 + (a[q] ^ '0') , mp.insert(i + j , vx * base[j] + vy); } } else if(opt == 2) { scanf("%d" , &x) , y = next[x] , next[x] = last[y] = 0 , vx = 0; for(i = 1 , p = x ; i < 50 && p ; i ++ , p = last[p]) { vx += (a[p] ^ '0') * base[i - 1] , vy = 0; for(j = 1 , q = y ; i + j <= 50 && q ; j ++ , q = next[q]) vy = vy * 233 + (a[q] ^ '0') , mp.erase(i + j , vx * base[j] + vy); } } else { scanf("%s%d" , str + 1 , &x) , vx = 0 , ans = 1; for(i = 1 ; i < x ; i ++ ) vx = vx * 233 + str[i]; for(i = x ; str[i] ; i ++ ) vx = vx * 233 + str[i] , ans = ans * mp.find(x , vx) % 998244353 , vx -= str[i - x + 1] * base[x - 1]; printf("%llu\n" , ans); } } return 0;}