前言 公约： 字符串默认下标从 0 开始 $s[l\dots r]$ 表示字符串 $s$ 的一个子串 $s_l s_{l+1} s_{l+2} \dots s_r$ 默认字符集为小写字母 KMP 前缀…

前言 省流：3.1KB->382 字符。 CodeGolf，即用尽一切手段得到最短解，允许在可接受的范围内牺牲一定的效率。本文限制编程语言为 C++14，环境以某 OJ 为准。 至于标题后面有个 1，…

二项式定理 二项式定理确实跟二项式反演有点关系，都是二项式，所以这里要提一句，证明都很显然就不说了。 定理如下： (a+b)n=∑i=0n(ni)aibn−i(a+b)^n=\sum\limits_{…

四边形不等式 对于一个代价函数 $w(l,r)$，如果对于任意的 $a\le b\le c\le d$，都满足： w(a,c)+w(b,d)≤w(a,d)+w(b,c)w(a,c)+w(b,d)\le…

前言 本文用于纪念自己过掉的第三道黑题（雾 前置芝士 树形 DP，树上背包 向量 凸包与闵可夫斯基和 差分 平衡树 题目大意 给定一棵 $n$ 个节点的带权无根树，节点编号 $1\sim n$。从中选…

前言 前置芝士：计算几何-向量 中的基础芝士。 此文用于纪念自己 A 的第二道黑题。 基本定理 定义 凸多边形：所有内角均在 $[0,\pi]$ 范围内的简单多边形。 凸包：平面上能包含点集中所有点的…

这是一道“约数容斥”的模板题。 思路 首先先不管 $\frac{x}{g}\ne 1,\frac{y}{g}\ne 1$ 这条限制。有 gcd 的计数题的常见技巧是考虑不同的 gcd 对于答案的贡献。…

第一类斯特林数 定义：将 $n$ 个不同元素划分进 $m$ 个相同的环（不可为空）的方案数，记为 $S_1(n,m)$ 或 ${n\brack m}$（{n\brack m}）。其中“环”指“旋转后重…

定义 本文中默认将正整数 $n$ 分解质因数得到 $n=\prod_{i=1}^{m} p_i^{c_i}$。 莫比乌斯函数的定义为： μ(n)={1n=10∃i,ci≥2(−1)m∀i,ci=1\m…

前言 笔记笔记笔记。彩色有助于我们观察式子。 单调队列优化 DP 首先我们需要了解单调队列优化 DP，这里给出两个经典题目：P10978 Fence & P10977 Cut the Sequ…