考虑枚举\(k\),那么起点的情况最多只有\(k\)种,因为显然对模\(k\)相同的位置作为起点是同构的。

利用异或的前缀和,我们就可以快速的得到确定\(k\)和确定起点以后项链的形态。

剩下为问题就是如何判断项链是否是对称的。

这是一个经典问题,我们把项链倍长,如果倍长后的字符串中存在一个子串是回文串且长度超过了倍长前字符串的长度,显然是存在对称轴的。

数\(n\)的因数个数最多有\(\2*sqrt{n}\)个,我们先考虑枚举\(k\)以后检验的复杂度,枚举起点需要复杂度为\(O(k)\),而匹配需要的复杂度是\(O(\frac{n}{k})\),所以复杂度为\(O(n)\),而枚举\(k\),最坏情况下复杂度为\(\2*sqrt{n}\),所以总的复杂度最坏情况下为\(O(2n*sqrt{n})\)。

 


发表评论

电子邮件地址不会被公开。 必填项已用*标注