一个奇妙的斯特林数推导

摘要:本文主要记录了对一道题目的非传统斯特林数解法。但在最近的一次更新中,我加入了用组合数解决问题的传统做法(也更简洁)。

Codeforces Round #576 (Div.1)

摘要:本文是对一场CF比赛的解析,用到的好方法有数的性质、随机化等。

Lyndon Word and The Runs Theorem

摘要:本文主要讲解了Lyndon Word的概念、性质,以及lyndon分解的计算方法,讲解思路较为清晰。但是本文尚未完成The Runs Theorem的部分。

Codeforces 1477F. Nezzar and Chocolate Bars

摘要:本文是对一道CF题的解析,主要运用了概率密度函数、生成函数。

Codeforces Round #700 (Div.1)

摘要:本文是对一场CF比赛的解析,象征着CF用户Mr_Spade终于取得了高中时错过的荣耀,登上了一个应属于自己的舞台,用到的好方法有整体二分、势函数、分段打表等。

旧题重做

摘要:本文是对曾经AC的一些好题的重新思考,主要涉及生成函数、容斥、自动机等知识点,含金量较高。

Codeforces 1427 G.One Billion Shades of Grey

摘要:本文是对一道CF题的解析,主要运用了数学结论以及网络流。

Codeforces Global Round 11 A-F题解

摘要:本文是对一场CF比赛的解析,象征着CF用户Mr_Spade的回归,用到的好方法有线性基、贪心等。

一般难度模板复习

(补充)证明线性递推相关的Hamilton-Cayley定理

[ZJOI2018]树

摘要:本文记录了著名的ZJOI2018 树的传统群论解法,主要以计数公式为核心。注意,现在已经普遍认为,有比本文提到的做法更OI化的方法。

将容斥系数隐含在式子中的方法

摘要:本文记录了一道我和雪菜共同出的题目,主要运用了隐含容斥系数的推导,是一道较为经典的OI好题,含金量较高。

老年选手康复训练

摘要:本文主要记录了我从学考中暂时回归竞赛时进行的恢复训练内容,主要涉及了当年重大赛事的题目,含金量较高。

UOJ #76 【UR #6】懒癌

摘要:本文对一道UOJ的题目进行了讲解。本题和传统OI题目风格差别较大,可以略读。

一些知识点的整理

摘要:本文是诸多实用技巧的总结,是一篇含金量较高的文章。主要讲解的内容有不定和式、点分治、最小割、时间线段树、四元环、四毛子等。

ZJOI2019 Day1 题解

摘要:本文是对ZJOI2019 Day1比赛的解析,El Psy Congroo.

Codeforces Round #545 (Div. 1)

摘要:本文是对一场CF比赛的解析,用到的好方法有强连通分量、凸壳、LCT等。

斯特林数与斯特林反演

摘要:介绍了第一类和第二类斯特林数,并给出了它们的平方递推公式,以及可以利用FFT加速的快速求解一行的技巧。此外,本文还介绍了斯特林反演。最后,本文附上了重构之前的历史版本。

AtCoder WTF 2019 C2. Triangular Lamps Hard

摘要:本文讲解了一道AtCoder题,主要运用了奇妙的推导和数位DP。

析合树

摘要:本文推到了连续段的性质,以此介绍了析合树的概念,并推导了较为实用的析合树生成算法。

Codeforces 1103 E. Radix sum

摘要:本文讲解了一道CF题,主要运用了取模理论,卷积定理以及初等的抽象代数方法(在多项式环模掉一个理想的域上做运算(如果你没有理解,这并不妨碍阅读,这只是我对交汇的知识的一种自说自话))。

Codeforces Round #539 (Div. 1)

摘要:本文是对一场CF比赛的解析,用到的好方法有平衡树、生成树计数、LCT等。

Codeforces 1097 G. Vladislav and a Great Legend

摘要:本文讲解了一道CF题,主要运用了树形dp,同时用到了树上背包证明树形dp的扩展版本。

万能欧几里得

摘要:本文主要推导了以直线与整点关系为目标的万能欧几里得算法,并给出了相关代码。

UOJ#424 【集训队作业2018】count

摘要:本文对一道UOJ的题目进行了讲解,主要通过数学推导,再进行矩阵优化表示和FFT解决。

LOJ#551 Matrix

摘要:本文对一道LOJ的题目进行了讲解,主要通过推导,再进行本地打表在线AC解决。

从分治乘法到快速沃尔什变换及其反演

摘要:本文介绍了一种从分治乘法的视角来推导集合幂级数卷积计算的视角,从而得到FWT是分治乘法的直接推论的结论。最后,本文还结合卷积定理给出了看待FWT的另一种方式。

洛谷P4831 Scarlet loves WenHuaKe

摘要:本文对一道洛谷题目进行了讲解,主要通过数学推导解决。

洛谷P5163 WD与地图

摘要:本文对一道洛谷题目进行了讲解,主要通过离线整体二分,再用并查集解决。

LOJ#6118 鬼牌

摘要:本文对一道LOJ的题目进行了讲解,主要通过数学推导解决。最后,本文还讨论了一种能够更高效解决问题的算法。

支配树

摘要:本文介绍了支配树的定义,并通过推导给出了近线性复杂度内求解支配树的公式。

线性插值

摘要:本文推导了实现线性插值的公式。注意,本文的推导实际上可以很方便地被拉格朗日插值公式取代,因此本文的推导没什么用,纯属娱乐。

求解形式幂级数的一阶微分方程

摘要:本文给出了一种涉及微分的方程的牛顿迭代解法。注意,本文的方法更多在理论复杂度上占优势,实际运用中往往分治FFT是更好的选择。

常系数齐次线性递推的黑科技及其证明

摘要:本文讲解了常系数齐次线性递推方法的矩阵证明,涉及了一些线性代数的理论。注意,首先本文的证明方法对于常系数齐次线性递推并非必要的;其次,本文对哈密顿-凯莱定理没有给出严谨的证明,如果你对证明有兴趣,可以看数学页中的相关文章。

Codeforces 1060 F. Shrinking Tree

摘要:本文讲解了一道CF题,主要运用了树形dp。注意,本文一定程度上混用了方案数和概率,有些难于理解,请小心食用。

多项式简明百科全书

摘要:本文介绍了除FFT以外所有多项式的常用算法,包括但不限于两类分治FFT,求逆、对数、指数、取模,牛顿迭代、常系数齐次线性递推等。

伸展树(Splay)复杂度证明

摘要:本文用势能分析法证明了Splay的复杂度。

二项式反演

摘要:介绍并证明了二项式反演,给出了一些初步应用。

min-max容斥-最值反演及其推广

摘要:介绍了min-max容斥,并给出了其证明。随后,文章还给出了min-max容斥的推广形式。

四边形不等式

摘要:本文介绍了四边形不等式及其应用,证明部分尚未完成。

网络最大流——最高标号预流推进

摘要:本文介绍了最高标号预流推进算法的过程,优化,并给出了代码。但是代码中似乎存在神秘的bug,请小心食用。

一般图最大匹配——带花树

摘要:本文介绍了带花树的原理,并证明了带花树的复杂度,但是因为神秘的原因没有给出代码。