2020-牛客多校-1

 ACM 󰈭 157字

F Periodicity Lemma

叉姐知乎专栏 https://zhuanlan.zhihu.com/which-way-did-the-bicycle-go

另一篇证明 https://zhuanlan.zhihu.com/p/89385360

原文 http://www.karlin.mff.cuni.cz/~holub/soubory/FineWilf.pdf

定理如下:

长为n的字符串S有循环节p、q,且满足p + q - gcd(p, q) <= n,那么有gcd(p, q)也是S的循环节。

已知上述结论后,那么为了比较$s^∞$与$t^∞$的字典序就可以只比较$|s| + |t| - gcd(|s|, |t|)$次。

真是高级的结论,证明及其数学思想留坑待补

J

伽马函数

Wallis’ integrals

I

一般图最大匹配?

2020-牛客多校-1
嗨! 这里是 rqdmap 的个人博客, 我正关注 GNU/Linux 桌面系统, Linux 内核 以及一切有趣的计算机技术! 希望我的内容能对你有所帮助~
如果你遇到了任何问题, 包括但不限于: 博客内容说明不清楚或错误; 样式版面混乱; 加密博客访问请求等问题, 请通过邮箱 rqdmap@gmail.com 联系我!
修改日志
  • 2023-09-01 18:14:49 单独划分ACM专题; 移动部分博客进入黑洞归档
  • 2023-05-29 23:05:14 博客结构与操作脚本重构
  • 2023-05-08 21:44:36 博客架构修改升级
  • 2022-11-16 01:27:34 迁移老博客文章内容