Description
给定小写字母组成的字符串 \(s\) 及正整数 \(m\)，求有多少小写字母组成的字符串 \(t\) 满足 \(t\) 的无穷重复中存在一个和 \(s\) 长度相同但比 \(s\) 字典序小的子串。
\(|s|,m\leq2000\)。
Solution
设 \(s=s_{1,n}\)，即 \(n=|s|\)（我们用 \(s_{a,b}\) 表示从 \(a\) 到 \(b\) 的子串）。
首先我们观察到一个性质：
引理 1
如果 \(s\) 的某个长为 \(t\) 的子串 \(s_{i,i+t-1}\) 字典序小于长为 \(i\) 的前缀 \(s_{1,t}\)，那么把 \(s\) 替换成 \(s_{1,i+t-2}\) ，答案是不变的。
证明也不难：如果 \(t\) 的无穷重复中有某个子串 \(p<s\)，那么要么 \(p_{1,i+t-2}<s_{1,i+t-2}\)，要么 \(p_{1,i+t-2}=s_{1,i+t-2}\) 而 \(p_{i+t-1,n}<s_{i+t-1,n}\)。
对于前者，显然 \(p_{1,i-1}\) 也是 \(t\) 的无穷重复的子串；对于后者，可以发现必有 \(p_{i+t-1}\leq s_{i+t-1}\)，从而 \(p_{i,i+t-1}\leq s_{i,i+t-1}<s_{1,t}\)，所以从 \(p_i\) 这一位开头的字符串字典序一定比 \(s_{i+t-2}\) 小。\(\square\)
举个例子：如果 \(s\) 为 egefd，由于 ef 大于 eg，因此如果有一个小于 \(s\) 的串在前三位和 \(s\) 相等的话第四位必定小于 \(s_4\) 也就是小于 f。那这样的话从这个串的第三位开头的串就是 e?*，其中 ?<d<g，因此这个串也一定比 ege 小。
同理我们也可以证明：如果 \(s\) 有某个 border，那么可以把这个 border 删去。
我们这样处理过 \(s\) 之后，它就满足：\(s\) 的任意子串大于等于 \(s\) 中与之等长的前缀；\(s\) 的任意后缀严格大于与之等长的前缀。称满足第一个条件的串叫做可做串，两个都满足的叫强可做串（因为我只会做这样的串），那么我们要求出 \(s\) 的最长可做前缀，并只考虑这个前缀。
至于如何处理，可以求一遍 KMP。假定 \(s\) 的长为 \(i-1\) 的前缀是强可做的，要求它的长为 \(i\) 的前缀是不是可做的。
假设有某个后缀 \(s_{t,i}\) 小于等长的前缀 \(s_{1,i-t+1}\)，那么肯定是 \(s_{1,i-t}=s_{t,i-1}\) 而 \(s_{i-1+1}>s_i\)（因为前面的都是可做的）。也就是说是一个 border 拼上一个字符。
但是因为前面的串是可做的，可以证明 KMP 那种跳最长 border 过程中字符是非升的，所以只需要判 \(i-1\) 处的最长 border 即可。这样的话就可以得到最长的可做后缀；然后不停判断是否存在 border，如果存在就删去即可。
现在我们得到了一个可做串 \(s\)。考虑用 \(26^m\) 减去不合法的情况，即从每个位置开始的子串字典序都大于等于 \(s\) 的情况。大于等于 \(s\) 等价于大于 \(pred(s)\)（最大的比 \(s\) 字典序小的字符串）。
只考虑 \(n\leq m\) 的情况（如果 \(m>n\)，那么只需要看一个前 \(m\) 位恰好等于 \(s_{1,m}\) 的串的重复是否比 \(s\) 小。根据 \(s\) 的强可做性，这个是必然的。因此只需要算大于 \(s\) 的情况即可，因为等于 \(s\) 也是合法的）。
由于 \(s\) 的后缀严格大于前缀，即 \(s_n>s_1\)，其 \(pred\) 就是将末尾减一的结果（不需要退位）。可以发现得到的串必定是可做的，即任意子串大于等于等长的前缀。
以下我们设 \(s\) 是可做的（就是之前那个 \(pred(s)\)），且 \(n=|s|<m\)，求有多少个长度为 \(m\) 的串 \(t\) 满足 \(t\) 的无穷重复的任意长度为 \(n\) 的子串都大于 \(s\)。
\(t\) 的无穷重复中任意子串大于 \(s\)，等价于说把 \(t\) 看成一个环之后，其任意长为 \(n\) 的子串字典序大于 \(s\)。下面我们先把 \(t\) 看成一个环。称满足条件的环是合法环。
定义一个串 \(p\) 是好的，当且仅当 \(|p|\leq n\)，且 \(p_{1,|p|-1}=s_{1,|p|-1}, p_{|p|}>s_{|p|}\)。
我们有如下引理：
引理 2
由若干个好串拼接而成的环 \(t\) 是合法环。并且对于任何一个合法环，将其表示成好串的拼接的方式是唯一的。
证明：引理有三个部分，我们分别证明：
- 先证明好串的拼接是合法的。如果有一个好串的拼接，对于其任意一个长为 \(n\) 的子串 \(q\)，\(q\) 一定有一个前缀 \(q_{1,k}\) 是某个好串的后缀。 设这个好串为 \(p\)，那么 \(q_{1,k}=p_{|p|-k+1,|p|}>s_{|p|-k+1,|p|}\geq s_{1,k}\)。其中大于号是因为好串的前面部分和 \(s\) 对应部分相等而最后一个字母大于 \(s\) 的对应字母， 大于等于号是因为 \(s\) 的可做性。于是 \(q_{1,k}>s_{1,k}\)，显然有 \(q>s\)。
- 再证明合法环可以分解成好串的拼接。对于一个合法环，找到其最小表示法 \(t\)（即，其循环排列中字典序最小者），那么从开头开始对 \(s\) 做匹配，每次发现某个位置比 \(s\) 的相应位置大的时候划分出一个好串。 只需要证明匹配到末尾的时候不可能还剩下没有匹配完的部分。如果到了末尾还没有匹配完，那么 \(t\) 必定有一个后缀与 \(s\) 的某个前缀相等（就是匹配剩下的部分）。 设 \(t_{|t|-k+1,|t|}=s_{1,k}\)，那么必定有 \(t_{1,k}=s_{1,k}\)，否则的话 \(t\) 的某个长度小于等于 \(k\) 的前缀是好串，而好串必定比 \(s\) 字典序大，这和 \(t\) 是最小表示不符； 但是既然 \(t_{1,k}=s_{1,k}\)，因为 \(t\) 实际上首尾是相邻的（是个环），所以 \(t_{|t|-k+1,|t|}+t_{1,k}=s_{1,k}+s_{1,k}\) 也是其子串，因此必须要大于等于 \(s_{1,2k}\)，即 \(s_{1,k}\geq s_{k+1,2k}\)， 这样的话，根据 \(s\) 的可做性又有 \(s_{k+1,2k}\geq s_{1,k}\)，于是 \(s_{1,k}=s_{k+1,2k}\)。这样的话必须有 \(t_{1,2k}=s_{1,2k}\)，因为 \(t\) 存在一个与 \(s_{1,2k}\) 相等的子串，而 \(t\) 是最小表示法从而 \(\leq s_{1,2k}\)， \(t\) 又是合法串因此 \(t_{1,2k}\geq s_{1,2k}\)。这样的话，重复之前的步骤，可以发现 \(s_{1,k}=s_{k+1,2k}=s_{2k+1,3k}=\dots\)，而 \(t_{1,pk}=s_{1,pk}\)。 当 \(p\) 充分大的时候，这说明 \(s\) 必须无限长，这显然是矛盾的，因此原来的假设（\(t\) 最后匹配好串没有匹配完）是不成立的。
- 最后要证明好串拆分是唯一的。事实上如果固定起点，那么好串划分一定是唯一的，即上面的构造方式；而任选 \(t\) 的某个最小表示法，根据上面的证明容易发现不可能存在跨越首尾的好串，于是可以直接从这个点开始划分。
这样，我们就完成了引理的证明。\(\square\)
这样的话，相当于对好串的拼接方式计数。显然对于某个长度，这个长度的好串个数是容易计算的（就是 ‘z’ 减去 \(s_i\)），那么设 \(a_i\) 表示长为 \(i\) 的好串个数，\(f_i\) 表示好串排成一排长度和为 \(i\) 的方案数，显然有
\[f_i=\sum_{j=1}^{\min(i,n)}a_jf_{i-j}\]
统计答案时，如果没有跨越首尾的好串，方案数就是 \(f_m\)；否则枚举跨越首尾的好串长度 \(i\)，方案数就是 \((i-1)a_if_{m-i}\)。
可以在 \(O(nm)\) 或者 \(O(n+m\log m)\)（多项式求逆）或者 \(O(n^2\log m)\)（常系数递推）或者 \(O(n\log n\log m)\)（多项式取模优化常系数递推）来求解。
下面是 \(O(n+m\log m)\) 的做法。NTT 板子是从论文哥那里抄的。
Code
1 |
|