「置顶」算法教程合辑


这个 idea 来源于 __stdcall 的教程合辑, 觉得这个很好, 所以学习了.

阅读全文

一些积性函数相关的简单筛法


useless algorithm 警告…

综述

记录了一些利用筛法求积性函数的方法.

阅读全文

博弈论初步:图上的游戏, Nim 游戏和 SG 定理


さぁ、ゲームをはじめよう
来吧,游戏开始了。

- NO GAME NO LIFE

综述

在 OI/XCPC 的范畴中, 博弈论的题目往往是在研究公平组合游戏, 似乎称为组合博弈论会好一点, 是寻常意义下的博弈论的一部分.

本文由有向图游戏开始, 到 Nim 游戏和 SG 定理结束, 介绍了一些简单的博弈论相关的内容.

阅读全文

泰勒公式的施勒米尔希-洛希余项备忘录


大一上学高数的时候室友就谈到这个东西, 当时没有注意, 后来…

阅读全文

牛顿二项式定理备忘录


数学就是用的时候不够用的东西 = =

综述

牛顿二项式定理是对二项式定理的推广, 也有人称之为广义二项式定理.

刚开始看 <组合数学> 的时候见到这个东西, 以为没什么用, 后来…

阅读全文

多项式与 FFT 备忘录


很多两年前学过的东西已经忘了, 虽然很大一部分原因在于当时就没有学明白, 但还是有一种原有的认知落空的感觉.

综述

在 OI/XCPC 中, FFT 常用于加速卷积的计算. 此外, 配合牛顿迭代得到的一系列多项式算法提供了对生成函数进行快速运算的方法, 因此在许多计数问题中也 FFT 也很有用.

阅读全文

2021 年 ICPC 陕西省赛的部分题解


比赛链接

铁牌作伴好还乡.

事实证明还是不要取一些诸如 “写的都不对” 之类的队名, 如果一语成谶就会非常尴尬 (

阅读全文

2022 年西安电子科技大学校赛的部分题解


题目 & 题面

被出题人打爆了.

阅读全文

Manacher 备忘录


一直记不住的 马拉车 板子. 前几天校内选拔赛还不会写, 惨遭吊打.

综述

对于一个长度为 $n$ 的字符串, Manacher 可以在 $O(n)$ 的时间内对每个位置 $i$ 计算一个类似于最长回文半径的东西.

具体而言, Manacher 在扫描每个位置的时候, 维护一个右端点最靠右的回文串的左右端点, 并借助于这个回文串来计算需要的信息.

阅读全文

我的 2021 年终总结


连年终总结都拖欠到新年的人是屑 (

阅读全文