题解 P6058 【后缀树 suffix】

StudyingFather · 2020-02-03 18:23:38 · 题解

第一个字母当然可以随便选。

问题来了，接下来的字母有什么限制呢？

其实很宽松，只需要不和第一个字母相同即可。

原因？根据题目的定义，后面的字母只要不和第一个字母相同，就不存在一种分割方案，将串 s 分割为 s_1，s_2，使得 s_1 是 s_2 的子串。否则的话，从第一个字母后分割就是一种合法的分割方案。

因此，第一个字母有 26 种选法，后面每个字母都不能和第一个字母相同，答案当然是：

使用快速幂计算上式即可通过本题。