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
一般图最大匹配?