# 后缀数组、相邻公共前缀与期望 出题人解法：用后缀数组和 LCP 统计不同子串及只出现一次的子串。Codex（GPT-6）：整数倍增排序、期望推导、64位询问、不可逆分母规则及检验。首选 [std.cpp](std.cpp)；另有完整的[后缀自动机解法](solution-alternative.zh.md)和 [alternative.cpp](alternative.cpp)。 ## 从计数到期望 记不同非空子串数为 $D$ ，其中恰出现一次的数量为 $U$ .整个字符串本身恰出现一次，因此 $U\ge1$ .每次成功率为 $p=U/D$ . 等待下一次成功的试验次数是几何分布，期望为 $1/p$ .达到 $N$ 次成功的总等待时间是 $N$ 段等待时间之和；由期望的线性性，答案为 $ND/U$ .次数包括最后一次成功的尝试，不能再减1。$N=0$ 的答案为0。 ## 后缀数组的两个计数式 按字典序排列所有后缀。令第 $i$ 个后缀长度为 $L_i$ ，它与前一个后缀的最长公共前缀为 $h_i$ ，边界 $h_0=h_n=0$ . $$D=\sum_{i=0}^{n-1}(L_i-h_i),\qquad U=\sum_{i=0}^{n-1}\bigl(L_i-\max(h_i,h_{i+1})\bigr).$$ 同一前缀对应的后缀在字典序中连续。因此，第 $i$ 个后缀中已在更早后缀出现过的前缀，恰是长度不超过 $h_i$ 的前缀，得到 $D$ 的公式。 对于是否在任何其他位置出现，只需看左右相邻后缀：若更远后缀共享某前缀，中间的相邻后缀也必共享。于是重复前缀的最大长度是 $\max(h_i,h_{i+1})$ .更长的前缀都只出现一次，而且不会由另一个后缀再次计入，得到 $U$ 的公式。重叠出现同样由不同后缀起点计数。 实现用整数排名倍增和两次稳定计数排序构建后缀数组，用线性 LCP 扫描求相邻公共前缀。整数排名给出确定的比较关系，无需浮点排名。 ## 正确处理模数 若 $P\nmid U$ ，直接计算 $(N\bmod P)(D\bmod P)U^{-1}\bmod P$ . 若 $P\mid U$ ，因为 $1\le U\le n(n+1)/2