2020-牛客多校-1

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

一般图最大匹配？