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

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

鲜花：我不信这辈子我学不懂 SA。 定义 $sa(i)$ 代表字符串 $s$ 字典序排名为 $i$ 的后缀的起始位置。 $rk(i)$ 起始位置为 $i$ 的后缀在所有后缀中字典序的排名。 二者满足 $sa(rk(i)) = rk(sa(i)) = i$。 $height(i)$ 为排名为 $i$ 和 $i - 1$ 的后缀的最长公共前缀长度。 后…

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

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

题目随记 https://47.94.97.204/contest/1694/problem/4 题目中直接给出了 $\frac a2$ 时间复杂度 $\log V$ 的提示太明显了，直接上套路即可。 https://www.luogu.com.cn/problem/P8036 由于 $[a, b]$ 一定有界，所以二分的条件应当是在 $[a, b…

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

``` \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$ 是一个因题而异的函数…