【算法介绍】原根与离散对数
文章总览：春风得意原根与离散对数，是非常玄学的概念（虽然说只是高联初等数论，但是本蒟蒻已经不会了），由于关于原根和阶的一些性质，我在搜索的过程中遇到了一个叫做群论的东西，这玩意对于我来说略有超纲有缘再见罢。这篇文章的内容限定于下。
阶的定义性质及其证明
原根的定义性质及其证明
原根的出现情况
如何求原根
指标的定义及其性质
互素情况下的指标计算（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$ 堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。
试设计出一个 ...
【拾题杂谈】BZOJ4260 CodeChef REBXOR
题面题目链接大秦 为你打开 题目传送门
备用题面给定一个含 $N$ 个元素的数组 $A$ ，下标从 $1$ 开始。请找出下面式子的最大值：
$(A[l1]⨁A[l1+1]⨁…⨁A[r1])+(A[l2]⨁A[l2+1]…⨁A[r2])$
其中 $1≤l1≤r1<l2≤r2≤N$，其中 $x\bigoplus y$ 表示 $x$ 和 $y$ 的按位异或。
思路首先要做这道题我们有个构想，就是一类经典题，要求两个不重叠也不相邻的连续异或和最大值。如果是不是异或和，单纯的是加和的话，我们一定有人会做，就是前后缀最大子段和相加。
那么如果是异或的话，我们有这样的性质。$a\bigoplus a =0$ 就是说相同的数异或就相当于没有异或，有了这个性质我们可以有前缀异或和。就是用 $sum[i]$ 表示 $A_1 \bigoplus A_2 \bigoplus \cdots \bigoplus A_i $ 的值，那么如果是区间 $[l,r]$ 之间的数的异或和，就可以用 $sum[r] \bigoplus sum[l - 1]$ 。
然后如果我们把前缀最大值和后缀最大值分开算的话，单独的 ...
【拾题杂谈】517九段第十课B
题面题目链接大秦 为你打开 题目传送门
备用题面给定了一个树（一个无环无向连通图）包含 $N$ 个节点，以及编号为 $1$ 到 $N−1$ 的边。
你需要执行以下两种指令：
CHANGE i t ：将第 $i$ 条边的费用改为 $t$ 。
QUERY a b ：询问从节点 $a$ 到节点 $b$ 的路径上的最大边费用。
思路基础构建首先我们要有一个共识，就是遇到这种树上边权操作的题目一定要往边权转化为点权的思路上想一想。为什么这么说呢，如果是点权的话，我们可以遍历啊等等各种方式去维护，但是如果是边权就会变得麻烦，因为两个点之间就是一条边，我们可以认为图是若干条点与点的关系构成的，那么维护点肯定比维护边要方便，因为我们的数据记在点上就可以通过给出的若干关系来得出答案。
那么这种题我们要如何把点权转化为边权呢？这就有一个常用技巧。对于树上一条边来说，我们习惯把边的信息记载儿子方向的点上面，因为对于树来说，一个父亲可以有多个儿子，但是一个儿子只能有一个父亲，这样的映射关系就告诉我们存在儿子方面一定不会有冲突。
那么如果我们把一个问题的边权转化成了点权，那么这道题就从一个修改边权的问题变成 ...
【算法介绍】字典树算法
算法简介：流光的星火$\tt Trie$ 树，已经在曾经的文章中提及，但是说呢，并没有多提应用以及一些细节，所以说我们单独开一篇文章来讲 $\tt Trie$ 树。
友情链接：
【算法介绍】字符串算法 | 祝馀宫
那么字典树字典树，形如其名，就是字典形状的树。我们就是基于字典的顺序来排列，会在下文提到。
算法引导：长明的烛火那么所谓字典顺序，就是我们在做字符串比大小的时候说的字典序。如果看过英文字典的话，就会发现一个这样的规律：
优先按照字典序排序，意思就是按照每一位的字符顺序排，越靠前的位置权值越大。比如说对于字符串 abcd 和 bcda 第一位 a 小于 b 所以说 abcd 小。
如果一个串是另一个串的前缀，则短的那一个小。比如说对于字符串 abc 和字符串 abcd 那么显然就是 abc 更小。
知道了这个字典序的顺序，那么我们字典树又是怎么个东西呢？首先我们要明确的一点是，这个字典树是一个新的数据结构，肯定不会是像数组一样列表式存储，我们要有内存上和形式上的优化。再结合字典树中的 “树” 这个关键词，我们大致会有这样的猜想。
树的节点，或者树的边表示一个字符，然后 ...
