Lyndon Word and The Runs Theorem
摘要:本文主要讲解了Lyndon Word的概念、性质,以及lyndon分解的计算方法,讲解思路较为清晰。但是本文尚未完成The Runs Theorem的部分。
2021-02-21
Codeforces Round #700 (Div.1)
摘要:本文是对一场CF比赛的解析,象征着CF用户Mr_Spade终于取得了高中时错过的荣耀,登上了一个应属于自己的舞台,用到的好方法有整体二分、势函数、分段打表等。
2021-02-08
一般难度模板复习
2020-10-10
(补充)证明线性递推相关的Hamilton-Cayley定理
2020-09-19
斯特林数与斯特林反演
摘要:介绍了第一类和第二类斯特林数,并给出了它们的平方递推公式,以及可以利用FFT加速的快速求解一行的技巧。此外,本文还介绍了斯特林反演。最后,本文附上了重构之前的历史版本。
2019-02-26
Codeforces 1103 E. Radix sum
摘要:本文讲解了一道CF题,主要运用了取模理论,卷积定理以及初等的抽象代数方法(在多项式环模掉一个理想的域上做运算(如果你没有理解,这并不妨碍阅读,这只是我对交汇的知识的一种自说自话))。
2019-02-17
Codeforces 1097 G. Vladislav and a Great Legend
摘要:本文讲解了一道CF题,主要运用了树形dp,同时用到了树上背包证明树形dp的扩展版本。
2019-02-14
从分治乘法到快速沃尔什变换及其反演
摘要:本文介绍了一种从分治乘法的视角来推导集合幂级数卷积计算的视角,从而得到FWT是分治乘法的直接推论的结论。最后,本文还结合卷积定理给出了看待FWT的另一种方式。
2019-01-01
常系数齐次线性递推的黑科技及其证明
摘要:本文讲解了常系数齐次线性递推方法的矩阵证明,涉及了一些线性代数的理论。注意,首先本文的证明方法对于常系数齐次线性递推并非必要的;其次,本文对哈密顿-凯莱定理没有给出严谨的证明,如果你对证明有兴趣,可以看数学页中的相关文章。
2018-10-22
Codeforces 1060 F. Shrinking Tree
摘要:本文讲解了一道CF题,主要运用了树形dp。注意,本文一定程度上混用了方案数和概率,有些难于理解,请小心食用。
2018-10-06