AcWing
  • 首页
  • 题库
  • 题解
  • 分享
  • 问答
  • 活动
  • 应用
  • 吐槽
  • 登录/注册

AcWing 141. 周期

作者: 作者的头像   yxc ,  2019-08-03 17:31:47 ,  阅读 1049


10


1

8 评论


用户头像
ZJZF   1个月前     回复

妙啊


用户头像
Bug_FreeOωO   1个月前     回复

5:41 p[1~next[i] 应该是和 p[i-next[i]+1~i] 是相等的吧


用户头像
Touma   4个月前     回复

设字符串a[1~n]长度为n.
这里的n % (n - nxt[n]) != 0则不存在非平凡循环节的推断不那么显然吧。
事实上我们定义$p$是一个“周期”,当且仅当$a_i = a_{i + p}$ (对$\forall i < n - p$ 成立)
定义$q$是一个“完美周期”,当且仅当n%p==0

那么当$p+q \le n$时候,若$p$是周期,$q$是周期,则$|p - q|$也是周期,从而$p$ % $q$也是周期,因此gcd(p, q)是周期。

注意到p = n - nxt[n]是一个周期,若p不完美,我们要证不存在完美周期。
反证:设完美周期为q>p(nxt性质),则有q <= n / 2,则p+q<=n, 于是gcd(p, q)是完美周期,且gcd(p, q)<=p也是周期,且为完美周期,矛盾。

用户头像
Touma   4个月前     回复

证明一下最后说的“显然不成立”的部分。


用户头像
Heisenberg_   5个月前     回复

淦!14.23秒y总表示不能用字符串hash代替这种情况 我就写了半个小时的字符串hash 呜呜呜

用户头像
yxc   4个月前     回复

hhh


用户头像
Heisenberg_   5个月前     回复

强烈建议把这道题加到基础课里面 呜呜 今天考这个题没写出来 在这看到了

用户头像
yxc   4个月前     回复

这道题目不基础呀hh 可以考虑放到提高课里。

你确定删除吗?

© 2018-2021 AcWing 版权所有  |  京ICP备17053197号-1
联系我们  |  常见问题
AcWing
请输入登录信息
更多登录方式: 微信图标 qq图标
请输入绑定的邮箱地址
请输入注册信息