快速幂 快速幂是在进行底数相同的乘法运算而幂数又极大的情况下使用的一种算法。 将幂次做二进制拆分，然后从低位到高位维护幂次积，同时若该位为 1 乘入答案。 模板 P1226 【模板】快速幂 12345678910111213141516171819202122#include<iostream>#include<cstdio>#define int un...

欧拉定理 欧拉定理：若 \(a\) 与 \(m\) 互质，则有 \[ a^{\varphi(m)}\equiv1(\mod m) \] 我们可以发现费马小定理其实就是欧拉定理的特殊情况。 证明的话，构造一个与 \(m\) 互质的数列操作，利用剩余系证明 扩展欧拉定理 扩展欧拉定理为 \[ a^b\equiv \begin{cases}a^{b\mod\varphi(p)},&...

贝祖定理 如果 \(a\)、\(b\) 是整数，那么一定存在整数 \(x\)、\(y\) 使得 \(ax+by=\gcd(a,b)\)。 换句话说，如果 \(ax+by=m\) 有解，那么 \(m\) 一定是 \(\gcd(a,b)\) 的若干倍。（可以来判断一个这样的式子有没有解） 有一个直接的应用就是 如果 \(ax+by=1\) 有解，那么 \(gcd(a,b)=1\)。 ...

我的第一篇洛谷博客就是扫描线。虽然那时候什么也不懂，也非常幼稚，甚至不知扫描线的原理是如何，只是一门心思地去做，就像面对未知的生活。 扫描线处理矩阵面积之和的问题，当然它们会有互相覆盖而不能直接加起来。 扫描线就是从下往上一次扫描“线”，然后用线将图分成多个区域，累加即可。用线段树记录横坐标此时扫描线处的长度。 用 Xi 表示第 \(i\) 条竖直的线（用来划分区间），用 l...

这是之前博客园的草稿，写得不好，本来想直接删除了事。然而，斜率优化是一个很重要也很基础的优化问题，是需要学习掌握的。但我现在没有精力写一篇新的文章了。 OI wiki: 斜率优化

斐波那契数列 \(F(0)=F(1)=1\) 或 \(F(1)=F(2)=1\)，\(F(i)=F(i-1)+F(i-2)\). 广义斐波那契数列在转移时有系数且首两项给定。 求法 注意到斐波那契数列的转移为一个矩阵乘 \[ \begin{bmatrix}F(i)&F(i-1)\end{bmatrix} \begin{bmatrix} 1&1\\ 1&...

斜堆 斜堆是个很有趣的东西。而且它有一些很有意思的性质。 斜堆的大概就是每次往堆里面插入一个元素的操作非常“有趣”。插入的节点从根节点开始。如果插入的元素值比所在根小，它会将根“挤下去”，即替代原先的根的位置，将原先的根连到它的左子树上。如果所在根节点为空，它直接插入到此节点上。如果插入的元素比根大，那么它就会先交换所在根的两个子树，然后再递归到原先根的左子树进行插入，直到它比所在根小或...

最大权闭合子图 闭合子图 定义有向图的一个闭合子图是该有向图的一个点集，其中这个点集中的所有点的出边连向的还是点集中的点。 最大权闭合子图 给有向图的点加一个点权，能得到的点权最大的闭合子图。 网络流模型 将所有正点权的点的点权全部加入答案。接下来我们将原来正点权的点变成负点权。现在图上全是负点，我们需要尽量选最少点权使图符合条件。 设超级源点和超级汇点。 将超级源向所有...

路径覆盖 路径覆盖指一个路径的集合中所有路径点集的并集为原图点集。最小路径覆盖使路径集合大小最小。 路径覆盖分为可否重复选点两种。可重复选点在建模中加大流量即可。 网络流模型 建超级源 \(S\) 和超级汇 \(T\)，将每个点拆点。 将 \(S\) 向所有点 \(i\) 连边，将所有点 \(i'\) 向 \(T\) 连边。 对于原图边集，每一条边 \(u\) 向 ...

POJ3041 这道题正解对于像我这种蒟蒻来说比较难以想到。 我们发现每次覆盖的只是一条线上的所有点。那么我们可以把它想象成一个二分图，两个集合分别是横轴和纵轴。 想一想，这实际上是不是就是x轴轴和纵轴的最大匹配？ 于是这就变成了一个板子匈牙利算法题目。 1234567891011121314151617181920212223242526272829303132333435363...