算法标签

• 图论（有向图、欧拉路径/回路）
• 组合数学
• 字符串处理
• 计数问题

问题分析

关键观察

两个字符串等价的条件是它们具有相同的二元组（长度为$2$的子串）频率分布。

这实际上定义了一个有向多重图：

• 顶点：字符 a, b, c（共$3$个顶点）
• 边：每个二元组对应一条有向边
• 边的多重性：二元组出现的次数

图论建模

对于字符串$s$，我们可以构建一个有向图$G$：

• 顶点集$V = \{\text{a}, \text{b}, \text{c}\}$
• 对于每个二元组$s[i]s[i+1]$，添加一条从$s[i]$到$s[i+1]$的有向边

重要性质：等价的字符串对应于具有相同边多重集的有向图。

解决方案

1. 图的基本性质

设：

• $in(v)$：顶点$v$的入度（指向$v$的边数）
• $out(v)$：顶点$v$的出度（从$v$出发的边数）
• $edges$：总边数（字符串长度减$1$）

2. BEST定理的应用

对于有向多重图的欧拉路径计数，可以使用BEST定理的推广形式。

情况1：欧拉回路 如果图是强连通的，且对于所有顶点$v$，有$in(v) = out(v)$，则存在欧拉回路。

等价字符串数量 = 有向图的生成树数量（由矩阵树定理计算）

情况2：欧拉路径 如果图是强连通的，且恰好有两个顶点的入度不等于出度（相差$1$），则存在欧拉路径。

等价字符串数量 = 从起点到终点的有向生成树数量

3. 具体计数公式

设字符集$\Sigma = \{\text{a}, \text{b}, \text{c}\}$，对于给定的字符串$s$：

1. 统计二元组频率：计算每个字符对$(x,y)$的出现次数$f_{xy}$
2. 计算顶点度数：
   • $out(x) = \sum_{y \in \Sigma} f_{xy}$
   • $in(y) = \sum_{x \in \Sigma} f_{xy}$
3. 检查连通性：确定图是否强连通
4. 应用计数公式：

主要结果：等价字符串的数量等于以特定顶点为根的有向生成树数量。

4. 矩阵表示

构建$3 \times 3$的拉普拉斯矩阵$L$：

• $L_{ii} = out(i)$（对角线元素）
• $L_{ij} = -f_{ij}$（非对角线元素，$i \neq j$）

删除第$k$行第$k$列得到$L_k$，则生成树数量 = $|\det(L_k)|$

算法步骤

预处理

1. 读取所有字符串
2. 对每个字符串统计二元组频率

对每个字符串处理

1. 统计边多重集：计算每个字符对的出现次数
2. 检查图性质：
   • 计算每个顶点的入度和出度
   • 检查强连通性
3. 计算等价类大小：
   • 如果不连通或度差过大：结果为$1$（只有自身）
   • 如果满足欧拉条件：应用矩阵树定理计算
4. 输出结果模$10^9+7$

时间复杂度

• 统计二元组：$O(L)$，其中$L$是字符串总长度
• 矩阵行列式计算：$O(3^3) = O(27)$（常数时间）
• 总复杂度：$O(L)$，满足$L \leq 10^6$的要求

样例验证

以abaa为例：

• 二元组：ab, ba, aa
• 图：a→b, b→a, a→a
• 顶点度数：out(a)=2, in(a)=2, out(b)=1, in(b)=1
• 强连通且满足欧拉回路条件
• 计算结果为$3$，符合样例

实现要点

1. 模运算：所有计算对$10^9+7$取模
2. 大数处理：使用64位整数避免溢出
3. 优化：预处理组合数，使用快速矩阵运算