Blog索引（置顶）

正不断走向开放的 $\rm OI$ 即将证明，历史的命运，必将掌握在无数奋斗者自己手中。 # $\mathscr Part\ \rm A\quad\large\textbf{知识}$ 记录成体系的一些知识总结，都是干货。 文章可能都比较长（$\rm 8Kb\sim128Kb$不等），请耐心阅读。 为了便于读者挑选文章，下面有几种标记 ： - $\color{blue}\large\circledcirc$ 意为“内容完善” - $\color{red}\large\circledcirc$ 意为“内容简略/尚不完整” - $\color{purple}\large\circleddash$ 意为“施工中/内容不严谨” - $\checkmark$ 意为“推荐” - $\dag$ 意为“过时/还有一定改进空间” # 1. 数学 - **幂级数科技** - [傅里叶变换(FFT)学习笔记](https://www.luogu.org/blog/command-block/fft-xue-xi-bi-ji) $\color{blue}\large\circledcirc$ $\dag$ 初二时写的，若有措辞拖沓，不严谨的情况请见谅。（已经过了小修小补） 避开了高度形式化和复杂的复数知识，可能比较适合初学者理解。 - [NTT与多项式全家桶](https://www.luogu.org/blog/command-block/ntt-yu-duo-xiang-shi-quan-jia-tong) $\color{blue}\large\circledcirc$ 板子的合集，推导过程较为详细。还有一系列 $O(n^2)$ 暴力递推做法。 提供（中度）模块化的数组式模板。 加更 $\rm EI$ 的高维多项式科技。 - [多项式计数杂谈](https://www.luogu.com.cn/blog/command-block/sheng-cheng-han-shuo-za-tan) $\color{blue}\large\circledcirc$ $\checkmark$ $\rm 2020.5$ 月完稿，总结了巨大量幂级数技术的技巧。 指明了技能树（包括数学部分 / 代码实现），含有较多例题。 其中也有进阶幂级数科技文章的索引，就不在此列出了。 - [位运算卷积(FWT) & 集合幂级数](https://www.luogu.org/blog/command-block/wei-yun-suan-juan-ji-yu-ji-kuo-zhan) $\color{blue}\large\circledcirc$ $\checkmark$ 包括经典的 $\rm FWT$ ，扩展后的 $k$ 进制 $\rm FWT$ ，以及子集卷积。 包括一些初等的集合幂级数内容。 - [半在线卷积小记](https://www.luogu.com.cn/blog/command-block/ban-zai-xian-juan-ji-xiao-ji) $\color{red}\large\circledcirc$ 多项式算法的一种性价比高的实现方式。（ $O(n\log^2n/\log\log n)$ 科技的先咕着…… - [转置原理小记](https://www.luogu.com.cn/blog/command-block/zhuai-zhi-yuan-li-xiao-ji) $\color{red}\large\circledcirc$ 利用转置原理洞察线性变换之间的微妙联系。 - [哑演算初探](https://www.luogu.com.cn/blog/command-block/ya-yan-suan-chu-tan) 哑演算的几个例子。 - **数论** - [莫比乌斯反演与数论函数](https://www.luogu.com.cn/blog/command-block/mu-bi-wu-si-fan-yan-ji-ji-ying-yong) $\color{blue}\large\circledcirc$ $\dag$ 本博客第一篇博文。由于古老陈旧可能没太大价值。 - [整除分块入门小记](https://www.luogu.com.cn/blog/command-block/zheng-chu-fen-kuai-ru-men-xiao-ji) $\color{blue}\large\circledcirc$ $\dag$ 经典整除分块。考虑加更非常规整除分块分析技巧。 - [杜教筛(+贝尔级数+powerful number)](https://www.luogu.com.cn/blog/command-block/du-jiao-shai) $\color{blue}\large\circledcirc$ $\checkmark$ 较为系统地论述了杜教筛理论的本质。 介绍了 powerful number 这一数论求和的有力（前沿？）工具。 利用贝尔级数分析积性函数，能够对杜教筛的能力范围给出明确的界定。 - [某种看起来不错的筛子](https://www.luogu.com.cn/blog/command-block/new-sieve) $\color{red}\large\circledcirc$ 关于积性函数筛法的一次尝试。 - [狄利克雷相关](https://www.luogu.com.cn/blog/command-block/gcd-juan-ji-xiao-ji) $\color{red}\large\circledcirc$ 包括狄利克雷前缀变换(快速积性函数卷积)以及 $\rm DGF$。 - [同余系基本定理1](https://www.luogu.com.cn/blog/command-block/tong-yu-xi1) $\color{blue}\large\circledcirc$ 包括逆元的引入，费马小定理，斐蜀定理，$\rm EXgcd$，欧拉定理，线性求逆等。 - [同余系基本定理2](https://www.luogu.com.cn/blog/command-block/tong-yu-xi2) $\color{blue}\large\circledcirc$ 包括 $\rm (EX)CRT,\ (EX)Lucas,\ Kummer$ 定理，扩展欧拉定理。 - [二次剩余小记](https://www.luogu.com.cn/blog/command-block/er-ci-sheng-yu-xiao-ji) $\color{blue}\large\circledcirc$ 单刀直入介绍了 $\rm Cipolla$ 算法。 - [原根&离散对数相关](https://www.luogu.com.cn/blog/command-block/yuan-gen-li-san-dui-shuo-xiang-guan) $\color{blue}\large\circledcirc$ 介绍了 $\rm (EX)BSGS$ ，以及求原根的方法，阶相关的性质。 - [Mr素性测试+Prho分解小记](https://www.luogu.com.cn/blog/command-block/mr-su-xing-ce-shi-prho-fen-xie-xiao-ji) $\color{blue}\large\circledcirc$ $\checkmark$ 较为详细地讲解了 `Prho` 分解，以及实用卡常技巧。 - [二次筛法分解小记](https://www.luogu.com.cn/blog/command-block/er-ci-shai-fa-fen-xie-xiao-ji) $\color{red}\large\circledcirc$ 关于一个亚指数分解算法的胡扯。（不实用） - **其他** - [炫酷反演魔术](https://www.luogu.com.cn/blog/command-block/xuan-ku-fan-yan-mo-shu) $\color{red}\large\circledcirc$ $\dag$ 介绍了反演的本质，以及 `OI` 中常见反演的证明和应用。 部分讲解还有待完善。 - [Min-Max容斥小记](https://www.luogu.com.cn/blog/command-block/min-max-rong-chi-xiao-ji) $\color{blue}\large\circledcirc$ - [单位根反演小记](https://www.luogu.com.cn/blog/command-block/dan-wei-gen-fan-yan-xiao-ji) $\color{blue}\large\circledcirc$ - [矩阵树定理(+行列式)](https://www.luogu.com.cn/blog/command-block/ju-zhen-shu-ding-li-xing-lie-shi-post) $\color{red}\large\circledcirc$ $\dag$ 介绍了行列式基本知识，以及没有证明的矩阵树板子总结。 - [群论小记](https://www.luogu.org/blog/command-block/qun-lun-xiao-ji) $\color{blue}\large\circledcirc$ 一些群论基本知识，$\rm Burnside$ 引理的证明，以及例题。 - [博弈论小记](https://www.luogu.com.cn/blog/command-block/bo-yi-lun-xiao-ji) $\color{red}\large\circledcirc$ 介绍了 $\rm SG$ 和，以及若干例题。（ $\rm SG$ 积先咕着 - [线性基小记](https://www.luogu.com.cn/blog/command-block/xian-xing-ji-xiao-ji) $\color{red}\large\circledcirc$ 从本质开始介绍线性基，可能有点难懂…… # 2. 数据结构 - [莫队略解](https://www.luogu.com.cn/blog/command-block/mu-dui-yang-xie) $\color{purple}\large\circleddash$ 一个没填完的坑。 - [一些常用的数据结构维护手法](https://www.luogu.com.cn/blog/command-block/yi-suo-chang-yong-di-shuo-ju-jie-gou-wei-hu-shou-fa) $\color{blue}\large\circledcirc$ $\dag$ 包括 $\rm CDQ$ 分治，线段树分治，整体二分，猫树分治，二进制分组。 介绍了算法基本原理，包含进阶例题（题单）。 - [树分治小记](https://www.luogu.com.cn/blog/command-block/shu-fen-zhi-xiao-ji) $\color{blue}\large\circledcirc$ $\checkmark$ 包括 (动态)(点/边/链)分治，全局平衡二叉树等。例题和技巧丰富。 - [LCT小记](https://www.luogu.com.cn/blog/command-block/lct-xiao-ji) $\color{blue}\large\circledcirc$ $\checkmark$ 简略的介绍了 $\rm LCT$ 的原理。包含若干进阶例题（维护子树/生成树）。 - [关于线段树上的一些进阶操作](https://www.luogu.com.cn/blog/command-block/guan-yu-xian-duan-shu-shang-di-yi-suo-jin-jie-cao-zuo) $\color{red}\large\circledcirc$ 包括兔队线段树，$\rm Seg-beats$，历史值标记，李超树四大部分。 - [动态DP小记](https://www.luogu.com.cn/blog/command-block/dong-tai-dp-xiao-ji) $\color{red}\large\circledcirc$ 简略地介绍将 $\rm DP$ 写成“矩阵变换”的方法，分析了若干例题。 - [动态图连通性问题](https://www.luogu.com.cn/blog/command-block/dong-tai-tu-lian-tong-xing-wen-ti) $\color{purple}\large\circleddash$ 尚无代码，不保证讲解正确。 - [KDT小记](https://www.luogu.com.cn/blog/command-block/kdt-xiao-ji) $\color{blue}\large\circledcirc$ $\checkmark$ 介绍了 $\rm KDT$ 的基本原理，带插入，带标记，乱搞，$\rm KDT$ 分治。 其中有较为详细的复杂度证明，简洁的代码实现。 - [分块相关杂谈](https://www.luogu.com.cn/blog/command-block/fen-kuai-xiang-guan-za-tan) $\color{blue}\large\circledcirc$ $\checkmark$ 从初识根号到大分块！ - [虚树小记](https://www.luogu.com.cn/blog/command-block/xu-shu-xiao-ji) $\color{purple}\large\circleddash$ 虚树的构造方法及相关证明。大量周边技巧。 ## 3. 其他 - **字符串** - [后缀自动机学习笔记(干货篇)](https://www.luogu.org/blog/command-block/hou-zhui-zi-dong-ji-xue-xi-bi-ji) $\color{blue}\large\circledcirc$ $\dag$ [后缀自动机学习笔记(应用篇)](https://www.luogu.org/blog/command-block/hou-zhui-zi-dong-ji-xue-xi-bi-ji-ying-yong-pian-post) $\color{blue}\large\circledcirc$ 前者介绍了 $\rm SAM$ 的理解性默写技巧。后者则是大量例题。 - [后缀数组与相关应用](https://www.luogu.com.cn/blog/command-block/hou-zhui-shuo-zu-yu-xiang-guan-ying-yong) $\color{purple}\large\circleddash$ 一个没填的坑,可能不会再填了。 - [Border理论小记](https://www.luogu.com.cn/blog/command-block/border-li-lun-xiao-ji) $\color{blue}\large\circledcirc$ 介绍了 $\rm Border$ 相关的若干性质和例题。 - [回文自动机小记](https://www.luogu.com.cn/blog/command-block/hui-wen-zi-dong-ji-xiao-ji) $\color{blue}\large\circledcirc$ 包括回文自动机的构造和若干例题。结合 $\rm Border$ 理论介绍了等差性质。 - [Lyndon & Runs](https://www.luogu.com.cn/blog/command-block/lyndon-runs) $\color{blue}\large\circledcirc$ $\checkmark$ 系统介绍了 $\text{Lyndon Word}$ 和 $\text{Runs}$ 相关理论，证明较为详细。 - [DP的决策单调性优化总结](https://www.luogu.com.cn/blog/command-block/dp-di-jue-ce-dan-diao-xing-you-hua-zong-jie) $\color{blue}\large\circledcirc$ $\dag$ 决策单调性的常见模型以及多种优化手段。 - [计算几何算法汇总](https://www.luogu.com.cn/blog/command-block/ji-suan-ji-he-suan-fa-hui-zong) $\color{blue}\large\circledcirc$ $\dag$ 紧靠代码对计算几何常用知识点进行了解释。包括较多例题。 - [网络流/二分图相关笔记(干货篇)](https://www.luogu.com.cn/blog/command-block/wang-lao-liu-er-fen-tu-xiang-guan-bi-ji-gan-huo-pian-post) $\color{blue}\large\circledcirc$ $\checkmark$ [网络流/二分图相关笔记(应用篇)](https://www.luogu.com.cn/blog/command-block/wang-lao-liu-xiang-guan-bi-ji) $\color{blue}\large\circledcirc$ $\checkmark$ 前者介绍了网络流的基本原理，以及大量模板（如 $\rm Dicnic$，原始对偶，负环费用流，最小割树等）。 包括二分图的若干重要定理，网络流建模的常见模型。 后者包括 $100+$ 道例题（大派送）以及简要讲解。 - [三元环小记(+四元环)](https://www.luogu.com.cn/blog/command-block/san-yuan-huan-xiao-ji-si-yuan-huan-post) $\color{red}\large\circledcirc$ 尚无代码，不保证讲解正确。 - [状压DP杂谈(+轮廓线,插头)](https://www.luogu.com.cn/blog/command-block/zhuang-ya-dp-za-tan) $\color{red}\large\circledcirc$ 简略地介绍了经典状压，轮廓线，插头 $\rm DP$。入门难度较低，更适合初学者而非练习者。 # $\mathscr Part\ \rm B\quad\large\textbf{记录}$ 日常刷题时，大部分的题目都会记录在博客中。目前**杂题记录分为七类** ： - 数学记录 - 数论记录 - DP (动态规划) 记录 - DS (数据结构) 记录 - Str (字符串) 记录 - NC (非传统题) 记录 - 图论记录 - ??记录 (~~我也不知道是啥但还是记一下吧~~) 大型比赛的题解也会纳入记录，有“比赛记录”前缀。[OI 赛事合集](https://www.luogu.com.cn/blog/command-block/oi-sai-shi-ge-ji) 此外，还有若干**专题记录** ： - [contest & vp 记录](https://www.luogu.com.cn/blog/command-block/contest-vp-ji-lu) 如题，记录线上比赛和模拟训练的成果。始于 $2021.03$。 - [ATC 做题记录](https://www.luogu.com.cn/blog/command-block/atc-zuo-ti-ji-lu) 在 ATC 摸索的记录。（其实有 https://kenkoooo.com/atcoder/#/table/command_block 就够了吧…… # $\mathscr Part\ \rm C\quad\textbf{Flowers}$ - **散文** - （2021.1 高一） [2020 : 启程](https://www.luogu.com.cn/blog/command-block/post-2020-qi-cheng) - （2022.2 高二） [我们的雨](https://www.luogu.com.cn/blog/command-block/our-rain) $\checkmark$ - （2022.3 高二） [读《纪念刘和珍君》有感](https://www.luogu.com.cn/blog/command-block/du-ji-nian-liu-hu-zhen-jun-you-gan) - （2023.1 高三）[城市与天空 其一](https://www.luogu.com.cn/blog/command-block/cheng-shi-yu-tian-kong-ji-yi) - （2023.1 高三）[城市与天空 其二](https://www.luogu.com.cn/blog/command-block/cheng-shi-yu-tian-kong-ji-er) - **小说** - （2021.9 高二）[记忆犹新](https://www.luogu.com.cn/blog/command-block/tan-hua-di-ji-yi) - （2022.12 高三）[火龙与热干面](https://www.luogu.com.cn/blog/command-block/huo-long-yu-re-gan-mian) $\checkmark$ - （2023.10）[荆棘的种子](https://www.luogu.com.cn/blog/command-block/jing-ji-di-zhong-zi) - **诗歌** - （2022.8 高三）[雨沫](https://www.luogu.com.cn/blog/command-block/yu-mo) - （2022.9 高三）[坠落](https://www.luogu.com.cn/blog/command-block/zhui-luo) $\checkmark$ - （2022.11 高三）[十月](https://www.luogu.com.cn/blog/command-block/shi-yue) - （2023.1 高三）[漂流](https://www.luogu.com.cn/blog/command-block/piao-liu) - （2023.1 高三）[九月](https://www.luogu.com.cn/blog/command-block/jiu-yue) - （2023.2 高三）[水镜](https://www.luogu.com.cn/blog/command-block/shui-jing) - （2023.4 高三）[分开陆地的鱼](https://www.luogu.com.cn/blog/command-block/fen-kai-lu-di-di-yu) - **记录** - [三年の忆](https://www.luogu.com.cn/blog/command-block/san-nian-yi) 初中的一些记录。 - [全新文化课生活の现状](https://www.luogu.com.cn/blog/command-block/quan-xin-wen-hua-ke-sheng-huo-xian-zhuang) 新学期和记忆。 （2023 年 8 月始） 总点赞数：~4400