command_block 的博客

command_block 的博客

Blog索引(真·置顶)

posted on 2018-08-17 21:33:13 | under 索引 |

正不断走向开放的 $\rm OI$ 即将证明,历史的命运,必将掌握在无数奋斗者自己手中。

(最后一次维护 : $2021.9.10$)

$\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)学习笔记 $\color{blue}\large\circledcirc$ $\dag$

      初二时写的,若有措辞拖沓,不严谨的情况请见谅。(已经过了小修小补)

      避开了高度形式化和复杂的复数知识,可能比较适合初学者理解。

    • NTT与多项式全家桶 $\color{blue}\large\circledcirc$

      板子的合集,推导过程较为详细。还有一系列 $O(n^2)$ 暴力递推做法。

      提供(中度)模块化的数组式模板。

      加更 $\rm EI$ 的高维多项式科技。

    • 多项式计数杂谈 $\color{blue}\large\circledcirc$ $\checkmark$

      $\rm 2020.5$ 月完稿,总结了巨大量幂级数技术的技巧。

      指明了技能树(包括数学部分 / 代码实现),含有较多例题。

      其中也有进阶幂级数科技文章的索引,就不在此列出了。

    • 位运算卷积(FWT) & 集合幂级数 $\color{blue}\large\circledcirc$ $\checkmark$

      包括经典的 $\rm FWT$ ,扩展后的 $k$ 进制 $\rm FWT$ ,以及子集卷积。

      包括一些初等的集合幂级数内容。

    • 半在线卷积小记 $\color{red}\large\circledcirc$

      多项式算法的一种性价比高的实现方式。( $O(n\log^2n/\log\log n)$ 科技的先咕着……

    • 转置原理小记 $\color{red}\large\circledcirc$

      利用转置原理洞察线性变换之间的微妙联系。

  • 数论

    • 莫比乌斯反演与数论函数 $\color{blue}\large\circledcirc$ $\dag$

      本博客第一篇博文。由于古老陈旧可能没太大价值。

    • 整除分块入门小记 $\color{blue}\large\circledcirc$ $\dag$

      经典整除分块。考虑加更非常规整除分块分析技巧。

    • 杜教筛(+贝尔级数+powerful number) $\color{blue}\large\circledcirc$ $\checkmark$

      较为系统地论述了杜教筛理论的本质。

      介绍了 powerful number 这一数论求和的有力(前沿?)工具。

      利用贝尔级数分析积性函数,能够对杜教筛的能力范围给出明确的界定。

    • 某种看起来不错的筛子 $\color{red}\large\circledcirc$

      关于积性函数筛法的一次尝试。

    • 狄利克雷相关 $\color{red}\large\circledcirc$

      包括狄利克雷前缀变换(快速积性函数卷积)以及 $\rm DGF$。

    • 同余系基本定理1 $\color{blue}\large\circledcirc$

      包括逆元的引入,费马小定理,斐蜀定理,$\rm EXgcd$,欧拉定理,线性求逆等。

    • 同余系基本定理2 $\color{blue}\large\circledcirc$

      包括 $\rm (EX)CRT,\ (EX)Lucas,\ Kummer$ 定理,扩展欧拉定理。

    • 二次剩余小记 $\color{blue}\large\circledcirc$

      单刀直入介绍了 $\rm Cipolla$ 算法。

    • 原根&离散对数相关 $\color{blue}\large\circledcirc$

      介绍了 $\rm (EX)BSGS$ ,以及求原根的方法,阶相关的性质。

    • Mr素性测试+Prho分解小记 $\color{blue}\large\circledcirc$ $\checkmark$

      较为详细地讲解了 Prho 分解,以及实用卡常技巧。

    • 二次筛法分解小记 $\color{red}\large\circledcirc$

      关于一个亚指数分解算法的胡扯。(不实用)

  • 其他

    • 炫酷反演魔术 $\color{red}\large\circledcirc$ $\dag$

      介绍了反演的本质,以及 OI 中常见反演的证明和应用。

      部分讲解还有待完善。

    • 矩阵树定理(+行列式) $\color{red}\large\circledcirc$ $\dag$

      介绍了行列式基本知识,以及没有证明的矩阵树板子总结。

    • 群论小记 $\color{blue}\large\circledcirc$

      一些群论基本知识,$\rm Burnside$ 引理的证明,以及例题。

    • 博弈论小记 $\color{red}\large\circledcirc$

      介绍了 $\rm SG$ 和,以及若干例题。( $\rm SG$ 积先咕着

    • 线性基小记 $\color{red}\large\circledcirc$

      从本质开始介绍线性基,可能有点难懂……

2. 数据结构

  • 莫队略解 $\color{purple}\large\circleddash$

    一个没填完的坑。

  • 一些常用的数据结构维护手法 $\color{blue}\large\circledcirc$ $\dag$

    包括 $\rm CDQ$ 分治,线段树分治,整体二分,猫树分治,二进制分组。

    介绍了算法基本原理,包含进阶例题(题单)。

  • 树分治小记 $\color{blue}\large\circledcirc$ $\checkmark$

    包括 (动态)(点/边/链)分治,全局平衡二叉树等。例题和技巧丰富。

  • LCT小记 $\color{blue}\large\circledcirc$ $\checkmark$

    简略的介绍了 $\rm LCT$ 的原理。包含若干进阶例题(维护子树/生成树)。

  • 关于线段树上的一些进阶操作 $\color{red}\large\circledcirc$

    包括兔队线段树,$\rm Seg-beats$,历史值标记,李超树四大部分。

  • 动态DP小记 $\color{red}\large\circledcirc$

    简略地介绍将 $\rm DP$ 写成“矩阵变换”的方法,分析了若干例题。

  • 动态图连通性问题 $\color{purple}\large\circleddash$

    尚无代码,不保证讲解正确。

  • KDT小记 $\color{blue}\large\circledcirc$ $\checkmark$

    介绍了 $\rm KDT$ 的基本原理,带插入,带标记,乱搞,$\rm KDT$ 分治。

    其中有较为详细的复杂度证明,简洁的代码实现。

  • 分块相关杂谈 $\color{blue}\large\circledcirc$ $\checkmark$

    从初识根号到大分块!

  • 虚树小记 $\color{purple}\large\circleddash$

    虚树的构造方法及相关证明。大量周边技巧。

3. 其他

  • 字符串

    一个没填的坑,可能不会再填了。

    介绍了 $\rm Border$ 相关的若干性质和例题。

    包括回文自动机的构造和若干例题。结合 $\rm Border$ 理论介绍了等差性质。

    系统介绍了 $\text{Lyndon Word}$ 和 $\text{Runs}$ 相关理论,证明较为详细。

  • DP的决策单调性优化总结 $\color{blue}\large\circledcirc$ $\dag$

    决策单调性的常见模型以及多种优化手段。

  • 计算几何算法汇总 $\color{blue}\large\circledcirc$ $\dag$

    紧靠代码对计算几何常用知识点进行了解释。包括较多例题。

  • 网络流/二分图相关笔记(干货篇) $\color{blue}\large\circledcirc$ $\checkmark$

    网络流/二分图相关笔记(应用篇) $\color{blue}\large\circledcirc$ $\checkmark$

    前者介绍了网络流的基本原理,以及大量模板(如 $\rm Dicnic$,原始对偶,负环费用流,最小割树等)。

    包括二分图的若干重要定理,网络流建模的常见模型。

    后者包括 $100+$ 道例题(大派送)以及简要讲解。

  • 三元环小记(+四元环) $\color{blue}\large\circledcirc$

    尚无代码,不保证讲解正确。

  • 状压DP杂谈(+轮廓线,插头) $\color{red}\large\circledcirc$

    简略地介绍了经典状压,轮廓线,插头 $\rm DP$。入门难度较低,更适合初学者而非练习者。

$\mathscr Part\ \rm B\quad\large\textbf{记录}$

日常刷题时,大部分的题目都会记录在博客中。目前杂题记录分为七类

  • 数学记录
  • 数论记录
  • DP (动态规划) 记录
  • DS (数据结构) 记录
  • Str (字符串) 记录
  • NC (非传统题) 记录
  • 图论记录
  • ??记录 (我也不知道是啥但还是记一下吧)

大型比赛的题解也会纳入记录,有“比赛记录”前缀。OI 赛事合集

此外,还有若干专题记录

$\mathscr Part\ \rm C\quad\textbf{奇怪的碎碎念}$