后缀数组、相邻公共前缀与期望¶
出题人解法：用后缀数组和 LCP 统计不同子串及只出现一次的子串。Codex（GPT-6）：整数倍增排序、期望推导、64位询问、不可逆分母规则及检验。首选 std.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\) .
同一前缀对应的后缀在字典序中连续。因此，第 \(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<P^2\) ，分母只有一个因子 \(P\) .若 \(P\mid N\) ，先把 \(N\) 和 \(U\) 都除以 \(P\) ；否则若 \(P\mid D\) ，把 \(D\) 和 \(U\) 都除以 \(P\) ；否则最简分母仍有 \(P\) ，输出 \(-1\) .剩余分母不含 \(P\) ，可求逆。非 \(P\) 因子的约分不改变模值，所以无需形成可能溢出的乘积 \(ND\) .
这个分支确实可达：\(S=a^{11879}b^2c^{84166}\) 有 \(U=1000000007\) 、\(D=1000096051\) .\(N=1\) 输出 \(-1\) ；\(N=P\) 输出96044；\(N=0\) 输出0。
复杂度与方案比较¶
时间 \(O(n\log n+Q+\log P)\) ，空间 \(O(n)\) .计数与询问均用64位；模乘的两个因子均先降到 \(P\) 以下。
后缀自动机按终点位置等价类直接统计出现次数，是另一种完整模型。在固定94字符集下构建为线性时间，但稠密转移数组需要 \(O(94n)\) 空间。两种实现均通过完整数据；后缀数组沿用出题人计数法，且本次实测空间更小，作为首选。共同的分数取模代码位于 expectation.hpp。
验证与性能¶
正式数据各运行五次，并单独测量峰值内存。标准程序最慢中位数 0.033904 秒，峰值 7.22 MiB。按2倍向上取整至0.5秒，参考时限为 0.5 秒。自动机程序最慢中位数 0.069435 秒，峰值 80.46 MiB，两者均通过。