差分约束系统 是一种特殊的 元一次不等式组，它包含 个变量，以及
个约束条件，每个条件是有两个变量做差构成的，形如 .
我们要解决的问题是：求一组解，使得所有的约束条件得到满足，否则判断出无解.
1. 变形
差分约束系统中的每个约束条件： 都可以变形成：
2. 转化
接下来，思考一个图论的问题。
dist[i] 是从起点到 地的最短距离
dist[j] 是从起点到 地的最短距离
是从 地到 地的路线长度（边权）
则
是必然的，否则 dist[i] 就不是最短的距离。
所以，在最短路算法中，其本质工作就是检查所有的边，确保图中所有的边都满足
这个条件。
到这里，我们发现这两个式子格式完全一样，但是虽然两者代数关系相同，但是想直接关联起来还是比较抽象。
我们不妨画一张这样的图，虚构一个不存在的“起点”，连一条虚边指向 ，边权为最短路 dist[i] 的值。
于是，根据单源最短路的定义，我们轻易知道，最短路不成立的情况就是有负环的情况。
所以对于不等式： 可以连接从 到
的一条边，连接所有不等式构成的边，构建出最后的图。
3. 实现
可以用 SPFA 来 ...
高维前缀和是对一维、二维前缀和的多维数据结构的推广。
核心求解思想：逐维前缀和
在了解高维前缀和之前，需要先学习逐维前缀和的实现。
我们一般用容斥原理来构建二维前缀和，但还有一种基础的做法，是逐维前缀和。它的做法是，先对一行或者一列做前缀和，然后再对另一维度做前缀和，这样，可以得到二维前缀和。
对于这种逐一维度做前缀和的做法，我们叫它逐维前缀和。推广一下，可以发现，这个做法也可以应对更多维度的数据结构。
概述
对于 维的数组 ，大小为 ，其前缀和 定义为
高维前缀和常用于解决二进制中的问题，大概因为二进制的维度（位）比较多，但是大小（两种选择：0
和 1）却比较小，从时间以及空间复杂度来说最利于做成算法题吧。
在算法竞赛中，高维前缀和常用来解决的问题是 子集和（sum over
subsets, SOS） 问题。
就是指，用高维前缀和来得到二进制数的子集之和，例如，二进制数
11，其子集有 00 01
10 11， 求得这几个子集的贡献之和。
这时我们发现，这似乎和动态规划中的状压DP有点像，没错，其实这个问题是状压DP的一种，所以这种问题也叫
SOS DP。
因此，高维前缀和是 ...
引言
区间GCD分块就是将前/后缀的GCD数组按照数值分块。
其数学原理是，对于任意长度的数组 ，固定其一端点后，不断向另一端延伸构成的前缀（或后缀）区间，其产生的不同
GCD 值的个数至多为
个，其中 是数组元素的最大值。
这里有两种方法，第一种是二分加st表的方法，时间复杂度为 ，第二种是离线的方法，时间复杂度为
，解决一些问题的时候更优。
正文
例题
【题目描述】
给定一个长度为 的正整数数组
。现在有 次独立询问，每次询问给定一个整数 。对于每个询问，你需要回答：数组中有多少个连续子区间
（），满足该区间的 ？
【数据范围】
询问的
第一种做法
st表可以快速得到区间gcd。对于任意一个区间，由于区间中的前/后缀gcd值最多只有
种，因此，我们可以二分查找前/后缀gcd值相同的边界，二分的时间复杂度是
。
对于例题，我们可以枚举所有的区间左边界，然后对前缀gcd进行分块，找到gcd值为
的右端点区间，得到答案。
第二种做法
这种做法有点像第一种做法的逆向思维，它不是固定一个点不动，然后让其往一个方向蔓延来找区间，而是一个一个的将点加入进已经分好的块中。
...
随机颜色编码（Color Coding）是由 Noga Alon 等人在 1995
年提出的一种极其天才的算法技巧。它的出现，几乎就是为了解决一类特定的“老大难”图论问题：在一个巨大的图中，寻找一个特定形状的“小结构”（且要求不能走回头路/节点不能重复）。
引言
想象你正在一个包含
个景点、
条道路的巨大风景区骑马。每个景点都有一个“花韵值”。你需要规划一条满足以下三个条件的路线：
不走回头路（简单路径）： 任何景点最多只能经过一次。
雅致要求： 途经所有景点的“花韵值总和”，必须恰好是数字 () 的倍数。
最省体力： 在满足前两点的基础上，骑马消耗的总体力最少。
对于这个问题，我们首先需要 get
到的点是，根据鸽巢原理，满足这些条件的简单路径，点的个数一定小于等于
。因为，从某个点作为起点出发，如果路径上到达两个点的前缀和同余，那么说明这两个点的中间的这一段的“花韵值总和”一定是
的倍数。
所以问题变成了，从这个图中找到一个小于等于 个点的简单路径，要求“花韵值之和”是
的倍数，并且要求路程最短。
若我们尝试用 dfs
来解决这个问题，遇到题目给了“菊花图”，显然会 ...
有向图游戏是一个经典的博弈游戏——实际上，大部分的公平组合游戏都可以转换为有向图游戏。
在一个有向无环图中，只有一个起点，上面有一个棋子，两个玩家轮流沿着有向边推动棋子，不能走的玩家判负。
By : OI Wiki
mex 函数
：不属于集合 的最小非负整数。 例如 、。
SG 函数
对于状态 和它的所有 个后继状态 ，定义 函数：
什么时候结束游戏：
定义没有后继状态的为必败态，也就是 函数为 的状态，此时 函数的值一定为 。
一个简单的巴什博弈问题： 有 个石子，小 A 先取，小 B
后取，可以取一颗或者两颗石子，不能不取，最后取的人失败，两人都非常聪明，问谁获胜。
此问题符合对有向图游戏的定义。
如果将每个状态视为一个节点，可以转化为一个博弈图：
联系上方说过的对必败态的定义，。
并且由此可以递归地得到所有点的 值：
然后惊奇的发现，在这个博弈图中， 等于 时小 A 败， 不等于 时小 A 胜。
推广一下，就是 余 不等于 的时候小 A 胜，否则小 B 胜。
if (n % 3 == 1) cout << B &l ...
曼哈顿距离（Manhattan
Distance）
解释：只能横着或竖着走，坐标上两点的距离。
假设存在两点 和
，则：
对于上方求曼哈顿距离的式子，有四种情况：
观察发现，上方四种情况中反复出现了两个值 和 。 发现对于四种情况，曼哈顿距离也就是：
例题应用 求到所有定点的最大曼哈顿距离最小：
AtCoder
ABC 178 E
Codeforces
1689 D
切比雪夫距离（Chebyshev
distance）
解释：各坐标数值差绝对值的最大值。
假设存在两点 和
，则：
这时忽然发现，之前曼哈顿距离得出的结论：
与切比雪夫距离的形式非常相似！并且如果将 A，B 两个点的坐标换成 与 ，这两个点的切比雪夫距离刚好等于 与 的曼哈顿距离。
那么可以得到另一个结论：
曼哈顿距离转切比雪夫距离
转化为
新坐标系下的切比雪夫距离，即为原坐标系下曼哈顿距离。
由上边的结论反向推导一下，得到了：
切比雪夫距离转曼哈顿距离
转化为
新坐标系下的曼哈顿距离，即为原坐标系下切比雪夫距离。
上方的例题中，正是利用了这个原理：
将曼哈顿距离转为切 ...
求单峰函数的极值点。
推荐使用黄金分割优化的三分 不止可以减少调用次数，进行常数上的优化
还可以避免大跨步的数值改变，减少由于精度导致的问题
typedef long double ld;const ld eps = 1e-10;const ld gold = (sqrtl(5) - 1) / 2;ld f(ld x) {}ld find() { ld l = -1e9, r = 1e9; while (r - l > eps) { auto midl = r - (r - l) * gold, midr = l + (r - l) * gold; if (f(midl) < f(midr)) l = midl; else r = midr; } return l;}
基本概念
线性基可以解决向量方面的问题，具体来说，它可以为一个向量空间确立一些基底，这些基底通过数乘运算可以表示向量空间中的所有向量
对于一个异或线性基，数乘运算之后，只有两种情况 ，以及其本身，因此看上去就是基底选或者不选
线性基的底层原理是高斯消元法，算法本质上在用代码模拟这个过程
成为基底的核心条件是“具备无法被组合的独立属性”，而它在阶梯矩阵中的最终座次，严格取决于消元后残存的最高维度的非零属性。
用高斯消元法构建线性基，本质上是一个从高维向低维逐层扫描的“沉淀”过程：
拿着一个新向量，从最高维开始向下俯视。如果它在当前维度的属性不为
，就面临两种判定：
遇阻则消：如果该维度已被老基底占据，就用老基底对其进行消元（抹掉当前维度的属性），让向量继续向更低维跌落。
遇空则入：如果该维度是空位，当前向量就立刻在此“入座”，成为该维度的专属基底。
这个过程最精妙的严谨性在于：当向量落入某一层空位时，我们可以百分之百确信，它比当前维度更高的所有属性，都已经在之前的层层下落中被老基底彻底消去了。因此，当前的空缺维度，就是它理所应当的最高专属座次。
生成线性基有两种方法，贪心法和高斯消元 ...
