专栏文章

一道题

WWrongAnswer_90Alive
个人记录参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@mip1jdy7
此快照首次捕获于
2025/12/03 04:38
3 个月前
此快照最后确认于
2025/12/03 04:38
3 个月前
查看原文
给定 nn 个串 T1…TnT_1\dots T_n，第 ii 个串有 wiw_i 的权值。再给定 mm 个串 S1…SmS_1\dots S_m，定义 f(i,u,v)f(i,u,v) 表示 TiT_i 是否能由 SuS_u 的一个后缀和 SvS_v 的一个前缀拼接而成，你要求出 ∑i∑u∑vf(i,u,v)wi\displaystyle\sum_i\sum_u\sum_v f(i,u,v)w_i。
首先是弱周期引理（WPL）。尝试自己推了一下。
如果一个长度为 nn 的串存在长度为 x,yx,y 的循环节，并且 x+y≤nx+y\leq n，则 gcd⁡(x,y)\gcd(x,y) 是 nn 的一个循环节。
其实比较显然。初始所有  mod x\bmod x 同余的位置是一个等价类。枚举 i∈[1,x]i\in[1,x]，因为 x+y≤nx+y\leq n，所以可以把 ii 和 (i+y) mod x(i+y)\bmod x 这个等价类合并，合并完了之后由扩展欧几里得的结论显然就有等价类数量变成了 (x,y)(x,y)。
回到原问题，只需要计算 TT 能被 Su,SvS_u,S_v 拼接成的 u,vu,v 的对数。考虑直接枚举 1≤j<len1\leq j<len，钦定 T[1,j]T[1,j] 是 SuS_u 的后缀，T[j+1,len]T[j+1,len] 是 SvS_v 的前缀，用哈希统计答案。但是这样显然会算重，一对 u,vu,v 可能会在多个 jj 上被统计，但是我们只想要一次。
接下来进行去重。首先求出 TT 的最小循环节 KK。分两种情况。

2K>len2K>len

也就是没有出现两个完整的周期。假设现在有一组 u,vu,v，他们在 j1,j2,j3j_1,j_2,j_3 的位置上都被统计上了。显然我们得到了两个循环节：j2−j1,j3−j2j_2-j_1,j_3-j_2，而 2min⁡(j2−j1,j3−j2)≤n2\min(j_2-j_1,j_3-j_2)\leq n，这样一定有一种周期出现了两次，所以不可能出现这种情况。所以固定 TT，一对 u,vu,v 最多被算两次。
考虑减去这两次的贡献，假设两次统计位置是 j1,j2j_1,j_2，则一定有 j2−j1j_2-j_1 是 TT 的一个循环节。
所以枚举 TT 的一个 border kk，再枚举 j<kj<k，钦定 TT 在 jj 和 n−k+jn-k+j 的这两个位置都能被 Su+SvS_u+S_v 劈开。所以只需要减去以 T[1,j+n−k]T[1,j+n-k] 为后缀的乘上 T[j+1,n]T[j+1,n] 为前缀的串的数量即可。
这个东西暴力计算复杂度应该是 border 长度之和的。考虑如何优化一下。首先有结论一个串的 border 形成了 log⁡\log 段等差数列，并且相邻两组的首项大小关系是至少减半。
所以考虑对于同一组的 border 一起处理。假设这组 border 长度是 k1,k2…kmk_1,k_2\dots k_m，其中 Δ=k1−k2=k2−k3…\Delta=k_1-k_2=k_2-k_3\dots，k1k_1 最大 kmk_m 最小。我们先预处理 nexinex_i 表示 T[i,n]T[i,n] 作为 SS 的前缀的出现次数，preipre_i 表示 T[1,i]T[1,i] 作为 SS 的后缀的出现次数，则需要枚举 1≤j<k11\leq j<k_1，计算 nexj+1×∑dpren−kd+jnex_{j+1}\times \sum_d pre_{n-k_d+j}。容易发现最多只会用到 prepre 的后 k1k_1 个元素，并且实际上查询的是 prex+prex+Δ+prex+2Δ…pre_{x}+pre_{x+\Delta}+pre_{x+2\Delta}\dots，这可以 O(k1)\mathcal O(k_1) 预处理。因为相邻两个数列的首项至少减半，所以 ∑k1=O(n)\sum k_1=\mathcal O(n)。

2K≤len2K\leq len

这说明一个循环节出现了两次。考虑一个 Su+SvS_u+S_v 是再哪些位置把 TT 劈开的。假设开头出现位置是 j1j_1，结尾出现位置是 jmj_m。
如果 K∣(jm−j1)K\vert(j_m-j_1)，如果中间有一个 j′j' 满足 K∤(j′−j1)K\nmid(j'-j_1)，根据 WPL，gcd⁡(j′−j1,K)\gcd(j'-j_1,K) 是这个串的循环节，这个东西小于 KK 所以一定不合法。
所以一定有相邻两次出现间隔都是 KK 的倍数。而且因为 KK 是循环节，所以如果 T[1,x](x>K)T[1,x](x>K) 是 SuS_u 的后缀，则 T[1,x−k]T[1,x-k] 也一定是 SuS_u 的后缀，这样我们可以推出这种情况下，相邻两次出现的位置的距离差一定是 KK。这种情况下，我们枚举 j,j+Kj,j+K，钦定 jj 和 j+Kj+K 都是合法的统计位置，做一个点减边容斥，令答案减去 prei+K×nexi+1pre_{i+K}\times nex_{i+1} 即可。
而如果 K∤(jm−j1)K\nmid(j_m-j_1)，根据 WPL 一定有 jm−j1+K>lenj_m-j_1+K>len，否则存在比 KK 更小的循环节。这种情况下，我们需要枚举所有长度小于 KK 的 border 来算第一种情况的过程，和第一种情况一样做就行了。

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...