UOJ Logo zx2003的博客

博客

CTS2019D2T2的一种非标算做法

2019-05-14 19:32:02 By zx2003

下午上台发言的时候有点呆滞,感觉讲的东西自己都听不懂。可能讲课水平不太行。

首先考虑计数所有子串均大于等于s的串的个数。

然后对串s建立KMP自动机,补齐26n条转移边的那种。

注意根据题意,部分跳回根的转移边是不合法的

之后枚举在自动机里走了无穷多个串s之后到达的节点是点u。

由这个定义,在自动机里,从点u出发行走完一个完整的串s之后,会回到点u自己。

于是我们只要解决在一张有向图上,一个点出发走m步回到自己的方案数即可。单次复杂度$O(m * n * 26)$

由于还要枚举点u,所以总的复杂度是$O(n^2m * 26)$

而且可以发现这个算法并不依赖于n与m的大小关系。

这样我们就能获得60分啦

实际上这个算法是有漏洞的。

一个点每条转移边并不是都能走。

想像一下,串s形如abdabc,我们现在在长度为5的前缀对应的节点上。

如果下一个字符是c,那么在这个无穷循环串中,我们就会获得一个子串abc,显然由此可以导出一个比s小的子串。

所以,每个点上所有不是跳回根的转移边只有字符最大的一条有用。

如果从根出发只走这样的转移边,那么会形成一个rho的形状。

考虑在这个rho上计数。

我们先算出$f_{i,j}$表示从根出发走i步,走到节点j的方案数。这一部分复杂度$O(nm)$。

然后还是跟之前一样枚举节点u。

如果u不经过根,那么路径唯一,方案数可以$O(1)$计算。

如果u经过根,那么枚举从u出发走几步才跳回根。这一部分复杂度也是$O(nm)$。

最后该算法总复杂度为$O(mn)$。

感觉rho的结构挺简洁的吧,不过考场上由于某些原因,并没有考虑过改进复杂度。

有没有老哥来把前面这个算法优化一下啊?

upd:

可能是可以优化的。

设生成函数F满足$f_i$为从根出发走$i$步第一次走回根的方案数。

F是可以直接在KMP过程中计算的。

所有节点走$m$步并且经过根的总方案数应该是$[x^m] (F' * x -F +1) * \frac{1}{1-F}$

复杂度应该是$O(n+mlogm)$。

评论

zhengjiarui
谢大佬!我现在懂了!
GCCCCCC
感谢巨佬 stO
mektpoy
讲课水平真的不太行 (临时工哭了

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。