一道题

· · 个人记录

给定 n 个串 T_1\dots T_n，第 i 个串有 w_i 的权值。再给定 m 个串 S_1\dots S_m，定义 f(i,u,v) 表示 T_i 是否能由 S_u 的一个后缀和 S_v 的一个前缀拼接而成，你要求出 \displaystyle\sum_i\sum_u\sum_v f(i,u,v)w_i。

首先是弱周期引理（WPL）。尝试自己推了一下。

如果一个长度为 n 的串存在长度为 x,y 的循环节，并且 x+y\leq n，则 \gcd(x,y) 是 n 的一个循环节。

其实比较显然。初始所有 \bmod x 同余的位置是一个等价类。枚举 i\in[1,x]，因为 x+y\leq n，所以可以把 i 和 (i+y)\bmod x 这个等价类合并，合并完了之后由扩展欧几里得的结论显然就有等价类数量变成了 (x,y)。

回到原问题，只需要计算 T 能被 S_u,S_v 拼接成的 u,v 的对数。考虑直接枚举 1\leq j<len，钦定 T[1,j] 是 S_u 的后缀，T[j+1,len] 是 S_v 的前缀，用哈希统计答案。但是这样显然会算重，一对 u,v 可能会在多个 j 上被统计，但是我们只想要一次。

接下来进行去重。首先求出 T 的最小循环节 K。分两种情况。

2K>len

也就是没有出现两个完整的周期。假设现在有一组 u,v，他们在 j_1,j_2,j_3 的位置上都被统计上了。显然我们得到了两个循环节：j_2-j_1,j_3-j_2，而 2\min(j_2-j_1,j_3-j_2)\leq n，这样一定有一种周期出现了两次，所以不可能出现这种情况。所以固定 T，一对 u,v 最多被算两次。

考虑减去这两次的贡献，假设两次统计位置是 j_1,j_2，则一定有 j_2-j_1 是 T 的一个循环节。

所以枚举 T 的一个 border k，再枚举 j<k，钦定 T 在 j 和 n-k+j 的这两个位置都能被 S_u+S_v 劈开。所以只需要减去以 T[1,j+n-k] 为后缀的乘上 T[j+1,n] 为前缀的串的数量即可。

这个东西暴力计算复杂度应该是 border 长度之和的。考虑如何优化一下。首先有结论一个串的 border 形成了 \log 段等差数列，并且相邻两组的首项大小关系是至少减半。

所以考虑对于同一组的 border 一起处理。假设这组 border 长度是 k_1,k_2\dots k_m，其中 \Delta=k_1-k_2=k_2-k_3\dots，k_1 最大 k_m 最小。我们先预处理 nex_i 表示 T[i,n] 作为 S 的前缀的出现次数，pre_i 表示 T[1,i] 作为 S 的后缀的出现次数，则需要枚举 1\leq j<k_1，计算 nex_{j+1}\times \sum_d pre_{n-k_d+j}。容易发现最多只会用到 pre 的后 k_1 个元素，并且实际上查询的是 pre_{x}+pre_{x+\Delta}+pre_{x+2\Delta}\dots，这可以 \mathcal O(k_1) 预处理。因为相邻两个数列的首项至少减半，所以 \sum k_1=\mathcal O(n)。

2K\leq len

这说明一个循环节出现了两次。考虑一个 S_u+S_v 是再哪些位置把 T 劈开的。假设开头出现位置是 j_1，结尾出现位置是 j_m。

如果 K\vert(j_m-j_1)，如果中间有一个 j' 满足 K\nmid(j'-j_1)，根据 WPL，\gcd(j'-j_1,K) 是这个串的循环节，这个东西小于 K 所以一定不合法。

所以一定有相邻两次出现间隔都是 K 的倍数。而且因为 K 是循环节，所以如果 T[1,x](x>K) 是 S_u 的后缀，则 T[1,x-k] 也一定是 S_u 的后缀，这样我们可以推出这种情况下，相邻两次出现的位置的距离差一定是 K。这种情况下，我们枚举 j,j+K，钦定 j 和 j+K 都是合法的统计位置，做一个点减边容斥，令答案减去 pre_{i+K}\times nex_{i+1} 即可。

而如果 K\nmid(j_m-j_1)，根据 WPL 一定有 j_m-j_1+K>len，否则存在比 K 更小的循环节。这种情况下，我们需要枚举所有长度小于 K 的 border 来算第一种情况的过程，和第一种情况一样做就行了。