什么是数学归纳法？ 数学归纳法的思想是 有限到无限 的递推逻辑，证明某个命题对其所有定义范围均成立，其本质是： 基例：证明命题在初始条件 $n = base$ 下成立。 归纳假设：假设某个命题在 $n = k$ 的时候成立。 归纳步骤：证明某个命题在 $n = k + 1$ 的时候也成立。 若上述条件均满足则说明命题对 $n \ge base$ 的…

组合数和基本组合数公式 鲜花：距离上一次整理数学知识还是在 202320232023 年，不知不觉已经过去了两年，真快啊…… 那个时候我还很菜，不过现在的我并没有成为之前想成为的样子。 组合数和基本…

鲜花：我不信这辈子我学不懂 SA。学了三次 SA 了，每学一次都有新的发现，完全不知道我之前在学什么。 定义 $sa (i)$ 代表字符串 $s$ 字典序排名为 $i$ 的后缀的起始位置。 $rk (i)$ 起始位置为 $i$ 的后缀在所有后缀中字典序的排名。 二者满足 $sa (rk (i)) = rk (sa (i)) = i$。 $height (i)$ …

高斯约旦 高斯约旦 这玩意每次学了老是要忘，有可能没有理解透彻，所以写一下。 高斯约旦会将矩阵变为对角矩阵，步骤如下： 枚举第 iii 行，接着枚举第 jjj 列，对于第 jjj 行的 Ai,jA_{i, j} Ai,j​ 变成 000，就需要用 jjj 行减去 Ai,jAi,idfrac {A_…

这篇文章受密码保护，输入密码才能阅读

题目随记 https://www.luogu.com.cn/problem/P10080 找到一个完美匹配后如果是偶数直接输出，否则可以探究如何调整使得新图合法， 调整出来的和旧图连上一定是一个环，且黑色边的数量为奇数。 https://47.94.97.204/contest/1694/problem/4 题目中直接给出了 $\frac a2$ …

这篇文章受密码保护，输入密码才能阅读

``` \documentclass[UTF8]{ctexart} \usepackage{geometry} \usepackage{fancyhdr} \usepackage{graphicx} \usepackage{array} \newcommand{\PreserveBackslash}[1]{\let\temp=\#1\let…

这篇文章受密码保护，输入密码才能阅读

``` 斜率优化 斜率优化的核心思想是将转移方程变为形如 $y = kx +b$ 的形式，这样我们就需要解决 $n$ 个线性规划问题。在第 $i$ 个线性规划问题当中，我们的点集是 $S$，同时有斜率 $k_i$，假设这个线性规划的最小答案（截距）为 $b_i$ 则会向点集中添加一个新点 $(x_i, f (b_i))$，$f$ 是一个因题而异的函数…