CTS2019 重复

一年前的题又翻出来看。 本来以为这题该说的都应该被说完了，结果发现它有两种几乎互不相干的做法。一种充满理论分析，最后导出了一个十分简洁的计算公式，时间复杂度碾压标算；另一种充满套路，很有经典字符串题风格，目前占据主流。 表面上看，甚至难以想象这两种思路竟然是针对同一道题。但我坚信这两种做法一定存在某种联系，于是有了本文。（好像这已经不是第一次写这种文章了。 ### 方法一 翻译一下题意，以下$n$均指$s$的长度。 > 求有多少长为$m$的串的无限重复中，至少包含一个字典序严格小于$s$的，长恰为$n$的子串 #### 模板串处理 我们暂时忘掉无限重复，把文本串当成一个一般的无限长串，重点研究$s$的性质。 假设$s=$`acab`，我们将发现任何小于$s$的长为$4$的串$t$，一定也包含一个子串小于$s'=$`ac`。这是因为，要么$t$的前两位已经比$s$小，那么此时$t[1,2]<$`ac`$=s'$；否则$t$的前两位为`ac`，而后两位小于`ab`，则$t[3,4]<$`ab`$<$`ac`$=s'$。 推广到一般情况，我们发现如果$s$存在长度不过半的后缀$s[i,n]$小于等于与之等长的前缀$s[1,n-i+1]$。那么考虑$s'=s[1,i-1]$，即$s$去掉该后缀的结果，我们有： > 任何小于$s$的长为$n$的串$t$，一定也包含一个子串小于$s'$。 证明与上述例子类似，$s,t$要么在前半段分出胜负，有$t[1,i-1]<s[1,i-1]=s'$；要么它们在后半段分出胜负，有$t[i,n]<s[i,n]\le s[1,n-i+1]=s'[1,n-i+1]$。（最后一步是因为$[i,n]$不过半） 原本包含$<s$的子串的文本串$T$也包含$<s'$的子串；反过来包含$<s'$的子串的$T$也显然包含$<s$的子串（因为$s'$是$s$的前缀）。因此我们将$s$替换为$s'$，合法串数量不变。 提一句题外话。我们可以注意到，不断删除$s$的后缀，到最后无法进一步删除时，得到的串就是$s$的lyndon分解中的第一个串。也即$s'$是一个lyndon word，它满足$s'$严格小于它的所有后缀。 下面我们直接称$s'$为$s$，因为它们在本题中是等价的。 #### 文本串处理 现在是时候把$m$和无限重复回想起来了。我们将问题补集转化为「无限重复中不包含$<s$的子串的串个数」。 我们把文本串看成一个字符环，那么无限重复中的任意子串都是环上的一段（可能自交）。 下面我将说明，任何满足要求（所有子串$\ge s$）的字符环$T$，一定能被以唯一一种方法地切分成每段长不超过$n$的若干段，使得对于每段$p$满足如下条件： 1. $p[1,|p|-1]=s[1,|p|-1]$。 2. 以$p$为前缀的任意长为$n$的字符串字典序$\ge s$。（也即若$|p|<n$，$p[|p|]>s[|p|]$；否则$p[|p|]\ge s[|p|]$）。 例如$s=$`ababc`，则`b`,`ad`,`ae`,`abac`,`ababc`,`ababf`都是满足要求的段。但`a`，`bb`，`abaa`不是满足要求的段。 显然，除非$p=s$，$p$应大于$s[1,|p|]$。容易看出$p$也是lyndon word，这一点非常重要，将在下述证明中反复出现。 （证明过程比较长，可以选择性跳过） - 第一，如果一个字符环能被上述方式切分，那么方案是唯一的。 - 考察字符环的某种切分$A$，假设还存在另一种切分$A'$与之不同。 - 这样一来，我们一定能在环上找出分别属于$A,A'$的段$[l,r],[l',r']$，使得$l\le l'\le r< r'$，或反之。不妨设$l\le l'\le r< r'$。 - 考虑$T[l',r]$。站在$p'$的角度，$T[l',r]=s[1,r-l'+1]$； - 但站在$p$的角度，因为它是lyndon word，应有$T[l',r]>T[l,r-l'+l]\ge s[1,r-l'+1]$。这显然是不可能的。 - 因此至多只可能有一种给环分段的方案。 - 第二，任何一个**合法**字符环都能被上述方式切分。 - 从字符环最小表示的开头开始，贪心地切分（一位一位看，能切就切）。 - 我们只需说明，不会出现到最后仍匹配了一段$s$的**真前缀**（如果恰好匹配了$s$也合法）的情形。 - 反证，设第一段为$p$，最后一段为$s$的真前缀为$q$。我可以断言$q+p<p$。 - 因为如果$|q|\ge|p|$，根据切分规则必有$q[1,|p|]=s[1,|p|]<p$； - 否则根据$s$是lyndon word，将其后缀替换成等长前缀必然使字典序变小，也即$(q+p)[1,|p|]=s[1,|q|]+s[1,|p|-|q|]\le s[1,|p|]<p$。特别地，若$p=s$，我们有$(q+p)[1,|p|]=s[1,|q|]+s[1,n-|q|]< s[1,n]=p$。 - 这样一来，从$q$开始才应该是字符环的最小表示，与假设矛盾。因此到最后一定恰好能匹配完，而不会出现遗留一段$s$的真前缀无法切分的情况。 - 第三，任何能被上述切分表示的字符环一定合法。 - 考察环上可自交子串的开头。 - 如果恰是某段的开头，则根据切分条件的第二条，显然成立。 - 否则因为每段是lyndon word，从段间开头的字典序严格大于从段头开头的字典序。由上一条也成立。 #### 最终做法 虽然上述证明比较繁琐，但是得到的结论却非常清新。因为我们已经可以用合法段的拼接直接表示答案。 设$a_i$表示长为$i$的合法短数，也即$\text{'z'}-s[i]+[i=n]$；$f_i$表示将若干合法段拼接成总长度为$i$的串的方案数，则最终答案（还需用$26^m$减去）可通过枚举跨起点的段长得到，即 $$ f_m+\sum_{i=2}^n (i-1)a_if_{m-i} $$ 而$f_i$可以通过形式简单的递推得到： $$ f_i=\sum_{j=1}^i a_jf_{i-j} $$ 到这一步明显可以$O(mn)$做。当然也可以更进一步，分治FFT做到$O(m\log^2 m)$，多项式求逆做到$O(m\log m)$，甚至是线性递推做到$O(n\log n \log m)$。这些并不是我们这里讨论的重点，因为这些机械的科技在天才的想法面前不免黯然失色。 然而有趣的是，得到这个结论，并不止这一条思路。 ### 方法二 考察$s$的KMP自动机，把文本串$T$拿上去匹配。依旧是补集转化。 我们设$0$号节点表示空串，$i$号节点表示长为$i$的前缀。称向根的转移为平凡转移，其余为非平凡转移。 很容易发现$T$合法（不含$<s$的长为$n$的子串）当且仅当每次走的非平凡转移边满足下述条件： > 该转移边是该节点即其$fail$树上所有祖先的所有**非平凡**转移边中，字符最大的那个。 若不满足，可以找到大于当前转移字符的最高祖先，从该祖先的位置开始匹配就能的到长为$|s|$的字典序$<s$的串，导致$T$不合法。 于是每个点能走的非平凡转移边个数$\le 1$，它们构成一个环基内向树和内向树的混合森林。 由于文本串是无限重复的，那么在足够远处，与$T[x]$处和$T[x+m]$处匹配到自动机上的位置应该相同。因此只需统计从某点开始走$m$步回到原处的方案数。 我们要么不走平凡转移边，那么只需考虑环基树每个环大小是否为$m$的约数。要么走至少一次平凡转移边，这样可以DP出$f_{i,j}$表示从$i$开始$j$步走到根的方案数，然后枚举第一次走平凡转移边的时刻即可统计答案。 表面上看，这两种方法似乎没有任何联系。 --- 上文说最终的自动机的非平凡转移构成一个「环基树和树的混合森林」。这句话固然没错，但是实际的情况比这简单的多。 如果我们先用方法一中的方法将$s$缩短，那么再对其建KMP自动机之后的结果是可以直接描述出来的： > $0 \sim n-1$分别有一条向后的边，此外$n$还向$1$有转移边。此外$i-1$号点向$0$有$\text{'z'}-s[i]$条平凡转移边。 我们发现，可以将$n$和$0$重合起来，产生的结果不变。这样KMP自动机变成了一个完美的$n$元环。 更为精妙的是，任何一个方法一中提到的的合法段，都可以对应为这个新自动机上的一条从$0$开始和结束、中途不经过$0$的路径；而任何一个合法环，都对应于新自动机上的一个回路。 我们再来考虑新自动机上的一个长为$m$的回路如何与$f_m+\sum_{i=2}^n (i-1)a_if_{m-i}$产生一一对应。 在方法二中，我们首先枚举点，然后考虑以它为始末的回路个数。那么我们换一个求和顺序，先枚举回路，然后乘上会统计到它的点数。 - 首先所有回路都会被$0$统计到，那么先加上$f_m$。 - 其次，枚举回路第一次返回$0$之前的点$i-1$，这条回路显然会被$i-1$个非$0$点统计到。同时从$i-1$返回$0$有$a_i$种方案，还需走$m-i$步，所以共有$a_if_{m-i}$条这样的回路，它们对答案的贡献为$(i-1)a_if_{m-i}$。 至此，我们完全用方法二的语言解读了方法一中的公式。 ### 代码 ```cpp #include<bits/stdc++.h> #define P 998244353 int n,m,i=1,j=2,x=26,f[5050]; char s[5050]; int main(){ scanf("%d%s",&m,s+1);n=strlen(s+1),n=n<m?n:m; for(;j<=n && s[i]<=s[j];j++) s[i]<s[j]?i=1:i++; --s[n=j-i];f[0]=1; for(i=1;i<=m;i++)for(j=1;j<=i && j<=n;j++) (f[i]+=1ll*('z'-s[j])*f[i-j]%P*(i<m?1:j)%P)%=P; for(i=1,j=m;j;j>>=1,x=1ll*x*x%P)if(j&1) i=1ll*i*x%P; std::cout<<(i-f[m]+P)%P<<'\n'; } ```