517九段第一课 B ：解方程
题面：解方程大秦 为你打开 题目传送门
备用题面看不了题目的看下面喵！
计算关于 $x, y$ 方程 $Ax+By+C=0$ 满足 $x_1\le x \le x_2,y_1\le y\le y_2$ 的整数解有多少个，其中给出 $A,B,C,x_1,x_2,y_1,y_2$ 并保证 $x_1\le x_2,y_1\le y_2$。
思路注意到方程可以化简为 $Ax+By=-C$，拓展欧几里得可以解决问题 $Ax+By=\gcd(A,B)$ 的问题，所以将方程中的未知数整体提取 $\frac{-C}{\gcd(A,B)}$，拓欧解出特解后乘回去，最后通过拓欧一般解计算公式
x = x_0 + \cfrac B {\gcd(A,B)} \times k ,y = y_0 - \cfrac A {\gcd(A,B)} \times k\quad(k ∈ Z)最后计算出合理的新的 $x,y$ 上下界即可。
关于无解和特解情况看代码。
代码12345678910111213141516171819202122232425262728293031323334353637383940414243 ...
【算法介绍】网络流相关
算法总览：散勇化晓摸幺鱼简单的来说，网络流问题，就是给出一张图，图上面有一个起点，被称作“源点”，还有一个终点，被称作“汇点”。而每一条边都有一个容量，超过容量就不可以通过这条边，有时候边还会有费用，通过这条边就需要花费这些费用。最终的目的就是从源点出发，不管你用什么方法走，最终汇集到汇点的流量最大、或者流量最大中的方案中费用最小的等等等等……这类问题，全都被称作为网络流问题或者流量问题，在生活中应该是非常常见的一种问题。
本文内容限定大纲如下：
网络流整体简介与符号规定
网络流经典问题类型
残量网络的定义
增广路与反向弧
最大流计算之 $\tt FF$ 方法
最大流计算之 $\tt EK$ 算法
最大流计算之 $\tt Dinic$ 算法
最大流计算之 $\tt Dinic$ 算法优化
最小割计算之最大流最小割定理
最小割计算之割集与变种
费用流计算之算法推导
算法基础：棋秤作枕好入眠
网络流整体简介与符号规定
网络流经典问题类型
残量网络的定义
增广路与反向弧
网络流基本概念OK啊各位，虽然一开始的文章总览提到了网络流问题的基础概念，但是这里还是补充一下详细的定义以及一些符号 ...
【算法介绍】杜教筛和 Min_25 筛
文章总览：童年虽然但是，我们熟知的筛法应该是欧拉筛和埃式筛等筛质数的筛，属于直观意义上的“筛子”；我们也知道，欧拉筛其实是可以筛积性函数的；但是这次的两个筛不太一样，他们的作用是在于快速计算积性函数前缀和，不过他们的实现手法和思想与这些直观意义上的筛子相近，所以也被称为“筛”。
下面是本文大纲：
狄利克雷卷积的定义与性质
狄利克雷卷积的两个重要结论
常见的积性函数及其计算方式
线性筛筛积性函数的推导
线性筛常见应用二则
杜教筛的推导
杜教筛的常见应用二则
Min_25 筛的推导
Min_25 筛的常见应用一则
前置知识：邂逅
狄利克雷卷积的定义与性质
狄利克雷卷积的两个重要结论
常见的积性函数及其计算方式
狄利克雷卷积基础狄利克雷卷积的定义非常简单，就是对于两个数论函数 $f(x),g(x)$，他们狄利克雷卷积后的结果 $h(x)$ 定义为：
h(x)=\sum_{d\mid x}f(d)g\left(\tfrac{x}{d}\right)=\sum_{ab=x}f(a)g(b)狄利克雷卷积的计算过程可以简单表示为 $h=f\ast g$ 然后我们就可以有如下狄利克雷卷积的性质 ...
【算法介绍】原根与离散对数
文章总览：春风得意原根与离散对数，是非常玄学的概念（虽然说只是高联初等数论，但是本蒟蒻已经不会了），由于关于原根和阶的一些性质，我在搜索的过程中遇到了一个叫做群论的东西，这玩意对于我来说略有超纲有缘再见罢。这篇文章的内容限定于下。
阶的定义性质及其证明
原根的定义性质及其证明
原根的出现情况
如何求原根
指标的定义及其性质
互素情况下的指标计算（BSGS，Baby-Step Giant-Step）
非互素情况下的指标计算（拓展 BSGS）
参考资料
前置知识：时运驰骋
阶的定义性质及其证明
阶的定义
阶的性质及其证明
阶的定义首先要知道原根，就需要一个非常重要的前置知识，没有它甚至连原根都算不出来，他就是阶。首先给出阶在数学上的定义。我们定义满足 $a^r\equiv 1\pmod p$ 其中 $\gcd(a,p)=1\ (p\gt 1)$ 的最小正整数 $r$ 是 $a$ 对模 $p$ 的阶，记作 $\delta_p(a)$ 。
定义非常好理解，但是始终是抽象的，我们可以大概的举几个例子。比如说下面的例子中我们都取 $p=7$：
当 $a = 2$ 时，我们可以枚举：
$ ...
【算法介绍】快速傅里叶变换
算法简介：无穷动！无穷快速傅里叶变换，是一种快速计算多项式乘法的算法。它通过快速的转换多项式的表现形式，从而快速计算多项式乘法。推导过程较为繁杂，代码也晦涩难懂，所以这篇文章旨在帮助各位快速理解快速傅里叶变换的一些知识。
友情链接：
【算法介绍】拉格朗日插值法 | 祝馀宫
算法基础：狂想者，呜咽首先说，为了方便下面的推导，我来简单说一下一会要用到的几个数学工具。
三角函数相关首先是三角函数，三角函数是为了我们后续的复数运算推导做准备的。三角函数，想必大家都不陌生，常用的就是锐角三角函数 sin , cos , tan 。假设我们有下面的直角三角形 $Rt_\triangle ABC$ （ $\angle \theta$ 是点 $A$ 所在的角，直角的顶点是 $B$，剩下一个节点是 $C$ ）
假设我们分别要求 $\sin\theta,\cos\theta$ 和 $\tan\theta$（ $0\lt \angle\theta \lt 90^\circ$），那么我们就设 $\angle \theta$ 所对的这条边为 $b$ 一般称作对边，夹在 $\angle\theta$ 和直角 ...
【算法介绍】可持久化相关数据结构
算法简介：彩色歌谣可持久化，字面意思就是持久，但是什么东西可以叫做持久呢？这一篇文章主要讲的是可持久化数据结构，也就是说，所谓可持久化其实是对于数据结构中所存储的数据的持久化，说直白一点，就是历史版本。你可以在任何时候查询任意时刻你维护的的任何数据的状态，这就是所谓的可持久化。
但是你看这里的标签，一排排打了一堆可持久化数据结构，似乎很繁杂，但是说呢其实这也没什么。这里的可持久化数据结构都是基于这个可持久化线段树来建立的，所以这篇文章就会从可持久化线段树开始，一步一步讲解。
友情链接：
线段树 | 祝馀宫【算法介绍】线段树合并 | 祝馀宫
算法基础：元气迸发那么首先我们知道，可持久化线段树也就是我们常说的主席树。它的一大作用是查询历史版本，但是在引入这个概念之前，我要先讲一个更加好理解的内容，先看题罢。
给出一个长度为 $n$ 的数组 $a$，一共有 $m$ 次查询，每次查询询问一个区间 $[l,r]$ 中的第 $k$ 小数字。
模型构建既然已经透露过线段树的风声，那我们肯定是也知道这道题要用线段树了。但是这个线段树该怎么建呢？总不能对于每一个区间都建立一个线段树吧，这显然是不可能 ...
【算法介绍】后缀数组
算法简介：高门的谒礼这个后缀数组，还真是个玄学玩意，模板题就是紫题啊，研究起来有点难度，这篇文章就是来讲后缀数组的。所谓后缀数组，其实就是一个字符串算法，而且极为抽象。
后缀数组的主要内容，就是把一个字符串的所有后缀给排好序标上号。但是它有一些奇怪应用，更是难上加难，但是理解了以后就很简单了，这篇文章的目的就是带大家看看后缀数组的全部过程。
算法推导：御驿的径迹那么我们刚刚就说过后缀数组的主要内容，就是把一个字符串的所有后缀排好序以后标号。那么首先我们就要知道，后缀是什么？我们首先给出后缀的一些定义。
后缀： 在一个字符串中对于任意的 $i\quad (1\le i\le n)$ ，后缀就是这个字符串的第 $i$ 个字符到最后一个字符的连续子串。注意注意，我们整篇文章字符串都是从 $1$ 开始的下标。
然后呢说，我们这里排序是根据字典序来排序的，所谓字典序，就是字面意思的字典顺序。两个字符串逐个字符比较，遇到第一个不一样的时候看两个字符谁的 ASCII 值小，小的那个更小。如果发现有一个字符串比对完了都没有分出大小（也就是一个字符串是另外一个字符串的前缀）那么短的那个小。
基本思 ...
【拾题杂谈】[USACO5.4] 周游加拿大Canada Tour
题面：周游加拿大Canada Tour题目描述你赢得了一场航空公司举办的比赛，奖品是一张加拿大环游机票。旅行在这家航空公司开放的最西边的城市开始，然后一直自西向东旅行，直到你到达最东边的城市，再由东向西返回，直到你回到开始的城市。除了旅行开始的城市之外，每个城市只能访问一次，因为开始的城市必定要被访问两次（在旅行的开始和结束）。
当然不允许使用其他公司的航线或者用其他的交通工具。
给出这个航空公司开放的城市的列表，和两两城市之间的直达航线列表。找出能够访问尽可能多的城市的路线，这条路线必须满足上述条件，也就是从列表中的第一个城市开始旅行，访问到列表中最后一个城市之后再返回第一个城市。
输入格式第 $1$ 行: 航空公司开放的城市数 $N$ 和将要列出的直达航线的数量 $V$。$N$ 是一个不大于 $100$ 的正整数。$V$ 是任意的正整数。
第 $2\sim N+1$ 行: 每行包括一个航空公司开放的城市名称。城市名称按照自西向东排列。不会出现两个城市在同一条经线上的情况。每个城市的名称都 是一个字符串，最多 $15$ 字节，由拉丁字母表上的字母组成；城市名称中没有空格。
第 $N+ ...
【奇技淫巧】我做到了一类特殊动态规划……
起因我满怀欢喜的打开洛谷，发现洛谷 USACO 的绿色DP只剩下了这道！于是粗略扫了一眼，马上编码，炸了！好吧看错了题，事情又变得疏忽迷离……
题面题目传送门
题目描述传说，数千年前圣帕特里克消灭了哞尔兰所有的蛇。然而，蛇们现在卷土重来了！圣帕特里克节是在每年的3月17日，所以Bessie要用彻底清除哞尔兰所有的蛇来纪念圣帕特里克。
Bessie装备了一个捕网，用来捕捉 $ N $ 组排成一行的蛇（ $ 1 \leq N \leq 400 $ ）。Bessie 必须按照这些组在这一行中出现的顺序捕捉每一组的所有蛇。每当 Bessie 抓完一组蛇之后，她就会将蛇放在笼子里，然后带着空的捕网开始捕捉下一组。
一个大小为 $ s $ 的捕网意味着 Bessie 可以抓住任意包含 $ g $ 条的一组蛇，其中 $ g \leq s $ 。然而，每当 Bessie 用大小为 $ s $ 的捕网抓住了一组 $ g $ 条蛇，就意味着浪费了 $ s-g $ 的空间。Bessie 可以任意设定捕网的初始大小，并且她可以改变 $ K $ 次捕网大小（ $ 1 \leq K<N $ ）。
请告诉 B ...
【奇技淫巧】环形动态规划设计
算法简介：占理不饶人环形动态规划，是我们做动归过程中极其常见的一种类型。它的推导过程有时候非常循规蹈矩，或者说存在一些特定的思路来搞定，正巧遇到了新的一种做法，于是写了这篇文章讲一下。
我们都知道，环形动态规划的特点，就是维护结构是一个环。环的特殊之处就是相对于线性结构，就是数组这类来说，数组只会影响前一个或者后一个，如果在开头或者结尾就溢出之类的。
但是如果是环状结构，就会发现他们的特殊处在于最后一个会影响第一个，第一个会影响最后一个，这样的存在让我们非常难受，于是乎，就会有下面几种特殊的方式来转化环状结构。
算法演示：最终解释权那么说到转化环结构，常见的有两个方式。
第一个，暴力点，常见的破环为链
第二个，斯文点，罕见的分讨结果
但是他们的相同之处在于都是运用一种转化来使环变为线性结构的形式，只不过表现形式不同而已。我们下面可以用两个例题来大致认识一下这两种方法。
算法例一：真火炼宝印直接上题！
题目大意在一个圆形操场的四周摆放 $N$ 堆石子，现要将石子有次序地合并成一堆，规定每次只能选相邻的 $2$ 堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。
试设计出一个 ...
