[洛谷P5404][CTS2019]重复

这个题感觉并不是很难,但是我想了好久(大约3天),我真的太菜了。
首先存在一个串小于这个东西不太好做,我们可以用总方案减去每个串都大于等于的方案数。
那么我们就得到了一个$O(nm \min(n,m))$的dp,我们按顺序dp字符,然后需要记录其前缀在原串后缀数组中的排名,以及后缀在kmp匹配中的位置(因为如果小于原串前缀的话就不合法了,大于的话对于接下来匹配没有意义,所以只需要记录等于的位置即可,那么就只和kmp的匹配位置有关)。这样子就是三维状态,转移$O(|\sum|)$。那么70分到手。
70分代码:

然后发现我们每一个kmp匹配的位置接下去的字符必须大于等于其所有nxt(包括其自身)在原串中接下去的字符,这意味着我们每次接下去之后只会回到这些字符中最大字符的fail,或者直接回到0。
那么我们的转移就只有两种情况了。原dp优化到了$O(n^3)$。
这个性质非常有用,我们现在kmp的匹配图就变成了类似这样的东西:

另外可以发现,每个kmp上的匹配位置有一个固定的值,使得该串在后缀数组中的排名大于等于这个值就说明答案合法。
我们直接dp貌似没有优化空间,考虑一下别的想法。
如果枚举这个串在原串后缀数组上的排名,我们考虑如何求解答案。直接做貌似不太行,我们可以考虑统计排名大于等于某个串的答案,最后再减一下。
设此时我们要处理的后缀为S。
我们可以分两种情况讨论,如果S是这个串的前缀,那么问题变成上面图中从一个点开始,走到终点为某些位置的长度为$m-len(S)$的路径条数。
否则我们可以枚举这个串与S不同的第一个位置,那么要使串大于等于S,这个位置上的字符必须大于S中的字符,那么加入这个字符之后kmp必定匹配到0去了。如果这是第i个字符,那么就是要$m-i$步从0走到某些位置。
这个我们预处理出0走到每个点的信息,然后枚举路径是否经过0,经过0的话就是一个卷积求第m次项,不经过0的话路径唯一,直接暴力即可。然后由于所需的路径长度不同,一开始需要一个fft来粘合这些信息。
所以总复杂度$O(n^2\lg n)$,感觉可能有$O(n^2)$做法,但是我暂时想不出来。

Tagged with:

发表评论