CTS2019 重复

BJpers2 · 2020-07-07 18:49:48 · 个人记录

一年前的题又翻出来看。

本来以为这题该说的都应该被说完了，结果发现它有两种几乎互不相干的做法。一种充满理论分析，最后导出了一个十分简洁的计算公式，时间复杂度碾压标算；另一种充满套路，很有经典字符串题风格，目前占据主流。

表面上看，甚至难以想象这两种思路竟然是针对同一道题。但我坚信这两种做法一定存在某种联系，于是有了本文。（好像这已经不是第一次写这种文章了。

方法一

翻译一下题意，以下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满足如下条件：

以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自动机之后的结果是可以直接描述出来的：

我们发现，可以将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}。

至此，我们完全用方法二的语言解读了方法一中的公式。

代码

#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';
}