算法基础简介
这篇文章主要介绍一些基础算法，为后面的进阶内容进行铺垫
一方面，这些内容可以让初学者对 OI 的一些思想有初步的认识；另一方面，本章介绍的大部分算法还会在以后的进阶内容中得到运用。
复杂度
复杂度分为两种，时间复杂度和空间复杂度
时间复杂度和空间复杂度是衡量一个算法效率的重要标准
基本操作数
因为不同计算机的硬件配置和运行实际条件不同，所以同一个算法在不同计算机上运行的速度会有一定的差距，并且实际的运行速度难以在理论上进行计算，实际测量又较为麻烦，所以我们通常考虑的不是算法运行的实际时间，而是算法运行所需要的基本操作的数量
在普通计算机上，加减乘除、访问变量（基本数据类型的变量，下同）、访问变量都可以看作是一次基本操作
对基本操作的计数或者是估测可以作为评判算法用时的指标
时间复杂度
衡量一个算法的快慢，一定要考虑数据规模的大小。所谓数据的规模，一般指输入的数字个数、输入给定的图中的点数以及边数等。一般来说，数据的规模越大，算法的用时就越长。而在算法竞赛中，我们衡量一个算法的效率时，最重要的不是看它在某个数据规模下的用时，而是看它的用时随数据规模增长的趋势，即 时间复杂度
考虑用时随数据规模变化的趋势的主要原因有以下几点：
- 现代计算机每秒可以处理数亿乃至更多次基本运算，因此我们处理的数据规模通常很大。如果算法 A 在规模为 $n$ 的数据上用时为 $100n$ 而算法 B 在规模为 $n$ 的数据上用时为 $n^2$，在数据规模小于 $100$ 时算法 B 用时更短，但在一秒钟内算法 A 可以处理数百万规模的数据，而算法 B 只能处理数万规模的数据。在允许算法执行时间更久时，时间复杂度对可处理数据规模的影响就会更加明显，远大于同一数据规模下用时的影响。
- 我们采用基本操作数来表示算法的用时，而不同的基本操作实际用时是不同的，例如加减法的用时远小于除法的用时。计算时间复杂度而忽略不同基本操作之间的区别以及一次基本操作与十次基本操作之间的区别，可以消除基本操作间用时不同的影响。
当然，算法的运行用时并非完全由输入规模决定，而是也与输入的内容相关。所以，时间复杂度又分为几种，例如：
- 最坏时间复杂度，即每个输入规模下用时最长的输入对应的时间复杂度。在算法竞赛中，由于输入可以在给定的数据范围内任意给定，我们为保证算法能够通过某个数据范围内的任何数据，一般考虑最坏时间复杂度。
- 平均（期望）时间复杂度，即每个输入规模下所有可能输入对应用时的平均值的复杂度（随机输入下期望用时的复杂度）。
所谓“用时随数据规模而增长的趋势”是一个模糊的概念，我们需要借助下文所介绍的 渐进符号 来形式化地表示时间复杂度。
渐进符号
简单来说，渐进符号忽略了一个函数中增长较慢的部分以及各项的系数（在时间复杂度相关分析中，系数一般被称作“常数”），而保留了可以用来表明该函数增长趋势的重要部分。
大 $\Theta$ 符号
对于函数 $f(n)$ 和 $g(n)$，$f(n)=\Theta(g(n))$，当且仅当 $\exists\ c_1, c_2, n_0 > 0$，使得 $\forall\ n \ge n_0, 0 \le c_1 \cdot g(n) \le f(n) \le c_2 \cdot g(n)$
也就是说，如果函数 $f(n) = \Theta(g(n))$，那么我们能找到两个正数 $c_1, c_2$ 使得 $f(n)$ 被 $c_1 \cdot g(n)$ 和 $c_2 \cdot g(n)$ 夹在中间
例如，$3n^2 + 5n - 3 = \Theta(n^2)$
大 $O$ 符号
$\Theta $ 符号同时分我们了一个函数的上下界，如果只知道一个函数的渐近上界，而不知道其渐近下界，可以使用 $O$ 符号。$f(n) = O(g(n))$，当且仅当 $\exists\ c, n_0$，使得 $ \forall\ n \ge n_0, 0 \le f(n) \le c \cdot g(n)$
研究时间复杂度时通常会使用 $O$ 符号，因为我们通常关注的是程序使用时的上界，而不关心其用时的下界
需要注意的是，这里的“上界“和”下界”是对于函数的变化趋势而言的，而不是对算法而言的。算法用时的上界对应的是“最坏时间的复杂度”而非大 $O$ 记号。所以，使用 $\Theta$ 记号表示最坏时间复杂度是完全可行的，甚至可以说 $\Theta$ 比 $O$ 更加精确，而使用 $O$ 记号的主要原因，一是有时我们只能证明时间复杂度的上界而无法证明其下界（一般出现在较为复杂的算法及复杂度分析）、二是 $O$ 在电脑上输入更加方便
大 $\Omega$ 符号
同样的，我们使用 $\Omega$ 符号来描述一个函数的渐近下界。$f(n) = \Omega(g(n))$，当且仅当 $\exists\ c, n_0$，使得$\forall\ n \ge n_0, 0 \le c \cdot g(n) \le f(n)$
常见性质
- $f(n) = \Theta(g(n)) \iff f(n) = O(g(n)) \wedge f(n) = \Omega(g(n))$
- $f_1(n) + f_2(n) = O(max(f_1(n), f_2(n)))$
- $f_1(n) \times f_2(n) = O(f_1(n) \times f_2(n))$
- $\forall\ a \neq 1,\ log_a n = O(log_2 n)$
由换底公式可以得知，任何对数函数无论底数为何，都具有相同的增长率，因此渐近时间复杂度中对数的底数一般省略不写
例子
for 循环
int n, m;
std::cin >> n >> m;
for(int i = 0; i < n; ++i)
for(int j = 0; j < n; ++j)
for(int k = 0; k < m; ++k)
std::cout << "Hello World!" << endl;
如果以输入的数值 $n$ 和 $m$ 的大小作为数据的规模，则上面这段代码的时间复杂度为 $\Theta(n^2m)$
DFS
在对一张 $n$ 个点 $m$ 条边的图进行 DFS 的时候，由于每个节点和每条边都只会被访问常数次，所以时间复杂度为 $\Theta(n+m)$
枚举
枚举（Enumerate）是基于已有知识来猜测答案的一种问题求解策略
枚举的思想就是不断的猜测，从可能的集合中一一尝试，然后再判断题目的条件是否成立
进行枚举时要注意以下几项：
- 建立简洁的数学模型，给出解空间
- 减少枚举的空间，避免不必要的时间开销
- 选择合适的枚举顺序
模拟
模拟就是用就是就是来模拟题目中要求的操作
模拟题目通常具有码量大、操作多、思路繁复的特点。由于它码量大，经常会出现难以查错的情况，如果在考试中写错是相当浪费时间的
注意事项
写模拟题时，遵循以下的建议有可能会提升做题速度：
- 在动手写代码之前，在草纸上尽可能地写好要实现的流程
- 在代码中，尽量把每个部分模块化，写成函数、结构体或类
- 对于一些可能重复用到的概念，可以统一转化，方便处理：如，某题给你 “YY-MM-DD 时：分” 把它抽取到一个函数，处理成秒，会减少概念混淆
- 调试时分块调试。模块化的好处就是可以方便的单独调某一部分
- 写代码的时候一定要思路清晰，不要想到什么写什么，要按照落在纸上的步骤写
实际上，上述步骤在解决其它类型的题目时也是很有帮助的
递归 & 分治 & 回溯
简介
分治（Divide and Conquer），字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或者更多相同货相似的子问题，直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并
回溯（Back Tracking），是一个类似于枚举的尝试过程，主要是在尝试的过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的方法，也就是“走不通就回头”
递归（Recursion），在数学和计算机科学中是指在函数的定义中使用函数自身的方法，在计算机科学中还额外指一种通过重复将问题分解为同类的子问题而解决问题的方法
递归的基本思想是某个函数直接或间接地调用自身，将原问题的求解转换为许多性质相同但是规模更小的子问题。求解是只需要关注如何把原问题划分为符合条件的子问题，而不需要过分关注这个子问题是如何被解决的
以下是一些有助于理解递归的例子：
- 如何给一堆数字排序？答：分成两半，先排序左半边在排序右半边，最后合并就可以了，至于怎么排序左边和右边，请重新阅读这句话
- 你今年几岁？答：去年的岁数加一岁，2001年我出生
递归在数学中非常常见。例如，集合论对自然数的正式定义是：1是一个自然数、每一个自然数都有一个后继，这一个后继也是自然数
递归代码拥有的最重要的两个特征：结束条件和自我调用。自我调用是在划分并解决子问题，而结束条件定义了最简子问题的答案
递归的优点
结构清晰，可读性强，便于理解算法
例如，用不同的方法实现归并排序：
//不使用递归的归并排序算法
template <typename T>
void merge_sort(vector<T> a) {
int n = a.size();
for (int seg = 1; seg < n; seg = seg + seg)
for (int start = 0; start < n - seg; start += seg + seg)
merge(a, start, start + seg - 1, std::min(start + seg + seg - 1, n - 1));
}
//使用递归的归并排序算法
template <typename T>
void merge_sort(vector<T> a, int front, int end) {
if (front >= end) return;
int mid = front + (end - front) / 2;
merge_sort(a, front, mid);
merge_sort(a, mid + 1, end);
merge(a, front, mid, end);
}
显而易见，使用递归的版本比不使用递归的版本更易理解：递归版本一目了然，先将左半部分排序，再将右半部分排序，最后将两部分合并。而非递归的版本充斥着各种难以理解的边界计算细节，容易出现bug且不易调试
递归的缺点
在程序的执行中，递归是利用堆栈来实现的。每当递归中进入一个函数调用，栈就会增加一层栈帧，每次函数返回是减少一层栈帧。而栈的大小并非无限，当递归的层数过多是，就会造成 栈溢出 的后果
显然，递归处理在进行归并排序时是高效的；但，在使用递归去数一头牛身上的毛时并不是高效的，因为堆栈会消耗额外的空间，而简单的递推不会消耗空间
递归的优化
尾递归
在上面的缺点中，我们提到递归在数据量大时可能出现栈溢出的问题，这个时候我们使用尾递归优化来解决这个问题。尾递归的概念非常简单，即把在递归中的调用自身放在函数的最后一步
由于在尾递归中，再次调用自身是函数的最后一步操作，所以不需要保留外层函数的调用记录，因为调用的位置和内部变量等信息都不会再次使用，所以尾递归优化可以有效的防止栈溢出
遗憾的是，尾递归优化需要编译器或解释器的支持，所以在使用时要确定你使用的语言有没有针对尾递归做优化（Python 没有）
贪心
贪心算法（Greedy algorithm)，是用计算机来模拟一个”贪心”的人做决策的过程。也就是说，这个人会十分的”贪”，每一步行动总是按照某种指标选取最优的操作，并不考虑以后可能造成的影响
可想而知，并不是所有的时候贪心法都能获得最优解，所以一般使用贪心法的时候，都要确保可以证明其正确性
适用范围
贪心算法在有最优子结构的问题中尤为有效。最优子结构的意思是问题能够分成子问题来解决，子问题的最优解能递推到最终问题的最优解
证明方法
贪心算法一般有两种证明方法：反证法和归纳法
- 反证法：如果交换方案中的任意两个元素或相邻的两个元素后答案不会变得更好，那么就可以推定目前的解已经是最优解了
- 归纳法：先算出边界情况的最优解 $F_n$，然后再证明：对于每个 $n$，$F_{n+1}$ 都可以由 $F_n$ 推导出结果
常见题型
在提高组难度以下的题目中，最常见的贪心有两种。
- 「我们将 XXX 按照某某顺序排序，然后按某种顺序（例如从小到大）选择」
- 「我们每次都取 XXX 中最大/小的东西，并更新 XXX」（有时「XXX 中最大/小的东西」可以优化，比如用优先队列维护）
二者的区别在于一种是离线的，先处理后选择；一种是在线的，边处理边选择
排序解法
用排序法常见的情况是输入一个包含几个（一般一到两个）权值的数组，通过排序然后遍历模拟计算的方法求出最优值
后悔解法
思路是无论当前的选项是否最优都接受，然后进行比较，如果选择之后不是最优了，则反悔，舍弃掉这个选项；否则，正式接受，如此往复
与动态规划的区别
贪心算法与动态规划的不同在于它对每个子问题的解决方案都做出选择，不能回退。动态规划则会保存以前的运算结果，并根据以前的结果对当前进行选择，有回退功能
排序
排序算法（Sorting algorithm）是一种将一组特定的数据按某种顺序进行排序的算法。排序的算法多种多样，性质也大不相同
性质
稳定性
稳定性是指相等的元素经过排序之后相对顺序是否发生了改变
拥有稳定性这一特性的算法会让原本有相等键值的纪录维持相对次序，即如果一个排序算法是稳定的，当有两个相等键值的纪录 $R$ 和 $S$，且在原本的列表中 $R$ 出现在 $S$ 之前，在排序过的列表中 $R$ 也将会是在 $S$ 之前
基数排序、计数排序、插入排序、冒泡排序、归并排序是稳定排序
选择排序、堆排序、快速排序不是稳定排序
时间复杂度
和我们在前面提到的时间复杂度一样，排序算法的时间复杂度不尽相同，在这里我们讨论算法的最坏时间复杂度，也就是它的上界
基于比较的排序算法的时间复杂度下限是 $O(n \ \log n)$ 的
当然也有不是 $O(n\ \log n)$ 的。例如，计数排序 的时间复杂度是 $O(n + w)$，其中 $w$ 代表输入数据的值域大小
以下是几种排序算法的比较
归并排序
待续
快速排序
待续
堆排序
待续
希尔排序
待续
计数排序
适用于已知范围的整数排序，通过计算每个元素出现的次数，然后按次数输出元素
步骤： 1. 找到数组中的最大值和最小值 2. 统计每个元素出现的次数 3. 根据次数输出排序后的数组
void countingSort(int arr[], int n) {
int max = *std::max_element(arr, arr + n);
int min = *std::min_element(arr, arr + n);
int range = max - min + 1;
std::vector<int> count(range), output(n);
for (int i = 0; i < n; i++) count[arr[i] - min]++;
for (int i = 1; i < range; i++) count[i] += count[i - 1];
for (int i = n - 1; i >= 0; i--) {
output[count[arr[i] - min] - 1] = arr[i];
count[arr[i] - min]--;
}
for (int i = 0; i < n; i++) arr[i] = output[i];
}
基数排序
通过对数字的每一位进行排序，从低位到高位逐步对整个数组进行排序
步骤： 1. 按照每个元素的个位、十位等依次进行稳定排序 2. 重复直到对所有位排序完成
int getMax(int arr[], int n) {
int max = arr[0];
for (int i = 1; i < n; i++)
if (arr[i] > max)
max = arr[i];
return max;
}
void countingSortForRadix(int arr[], int n, int exp) {
std::vector<int> output(n);
int count[10] = {0};
for (int i = 0; i < n; i++)
count[(arr[i] / exp) % 10]++;
for (int i = 1; i < 10; i++)
count[i] += count[i - 1];
for (int i = n - 1; i >= 0; i--) {
output[count[(arr[i] / exp) % 10] - 1] = arr[i];
count[(arr[i] / exp) % 10]--;
}
for (int i = 0; i < n; i++)
arr[i] = output[i];
}
void radixSort(int arr[], int n) {
int max = getMax(arr, n);
for (int exp = 1; max / exp > 0; exp *= 10)
countingSortForRadix(arr, n, exp);
}
桶排序
将元素分到不同的桶中，分别对每个桶进行排序，然后将所有桶中的元素合并
步骤： 1. 将元素分配到多个桶中 2. 对每个桶中的元素进行排序 3. 合并所有桶中的元素
void bucketSort(float arr[], int n) {
std::vector<float> bucket[n];
for (int i = 0; i < n; i++) {
int bucketIndex = n * arr[i];
bucket[bucketIndex].push_back(arr[i]);
}
for (int i = 0; i < n; i++)
std::sort(bucket[i].begin(), bucket[i].end());
int index = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < bucket[i].size(); j++) {
arr[index++] = bucket[i][j];
}
}
}
锦标赛排序
待续
前缀和 & 差分
前缀和
前缀和是一种重要的预处理，可以大大降低查询时的时间复杂度，可以简单的理解为”数列的前 $n$ 项和”
C++标准库中实现了前缀和函数 std::partial_sum，定义于头文件 <numeric> 中
例题
二维/多维前缀和
多维前缀和的普通求解方法几乎都是基于容斥原理
示例：一维前缀和扩展到二维前缀和
比如我们有这样一个矩阵 $a$，可以视为二维数组：
1 2 4 3
5 1 2 4
6 3 5 9
那么我们定义一个矩阵 $sum$ 使得 $sum_{x,y}=\sum\limits_{i=1}^x \sum\limits_{j=1}^y a_{i,j}$
那么我们可以得到下面的矩阵：
1 3 7 10
6 9 15 22
12 18 29 45
这个前缀和中递推求 $sum$ 的过程也就是这个方程：$sum_{i,j}=sum_{i-1, j} + sum_{i, j-1} - sum_{i-1, j-1} + a_{i, j}$
因为我们同时加了 $sum_{i-1, j}$ 和 $sum_{i, j-1}$，所以我们重复加了一次 $sum_{i-1, j-1}$，故减去
所以，在我们求如 $(x_1, y_1) - (x_2, y_2)$ 子矩阵的和的时候，可以容易的通过类似的思考过程得出子矩阵的和为：
$sum_{x_2, y_2} - sum_{x_1 - 1, y_2} - sum_{x_2, y_1 - 1} + sum_{x_1 - 1, y_1 - 1}$
基于DP的高维前缀和
待续
树上前缀和
待续
差分
差分是一种和前缀和相对应的策略，可以当做是求和的逆运算
这种策略的定义是令 $b_i=\left\{\begin{array}{ll} a_i - a_{i-1} & i \in [2, n] \\ a_1 & i = 1 \\ \end{array} \right. $
简单性质：
- $a_i$ 的值是 $b_i$ 的前缀和，即 $a_n = \sum\limits_{i=1}^n b_i$
- 计算 $a_i$ 的前缀和 $sum = \sum\limits_{i=1}^n a_i = \sum\limits_{i=1}^n \sum\limits_{j=1}^i b_j = \sum\limits_i^n(n - i + 1) b_i$
树上差分
待续
二分
本小结简单介绍二分法及其衍生出的三分法和二分答案
二分法
二分查找（binary search），也称折半搜索（half-interval search）、对数搜索（logarithmic search），是用来在一个有序数组中查找某一元素的算法
工作原理
以在一个升序数组中查找一个数为例
它每次考察数组当前部分的中间元素，如果中间元素刚好是要找的，就结束搜索过程；如果中间元素小于所查找的值，那么左侧的只会更小，不会有所查找的元素，只需到右侧查找；如果中间元素大于所查找的值同理，只需到左侧查找
性质
时间复杂度
二分查找的最优时间复杂度为 $O(1)$
二分查找的平均时间复杂度和最坏时间复杂度均为 $O(\log n)$。因为在二分搜索过程中，算法每次都把查询的区间减半，所以对于一个长度为 $n$ 的数组，至多会进行 $O(\log n)$ 次查找。
空间复杂度
迭代版本的二分查找的空间复杂度为 $O(1)$
递归（无尾调用消除）版本的二分查找的空间复杂度为 $O(\log n)$
代码实现
int binary_search(int start, int end, int key)
{
int ret = 1;
int mid = 0;
while (start <= end)
{
mid = start + ((end - start) >> 1); // 直接平均有溢出可能
if (array[mid] < key)
start = mid + 1;
else if (array[mid] > key)
end = mid - 1;
else
{
ret = mid;
break;
}
}
return ret;
}
STL 中的二分查找
C++ 标准库中实现了查找首个不小于给定值的元素的函数 std::lower_bound 和查找首个大于给定值的元素的函数 std::upper_bound，二者均定义于头文件 <algorithm> 中
二者均采用二分实现，所以调用前必须保证元素有序
二分答案
解题的时候往往会考虑枚举答案然后检验枚举的值是否正确。若满足单调性，则满足使用二分法的条件。把这里的枚举换成二分，就变成了“二分答案”
例题
伐木工人 Mirko 需要砍 M 米长的木材。对 Mirko 来说这是很简单的工作，因为他有一个漂亮的新伐木机，可以如野火一般砍伐森林。不过，Mirko 只被允许砍伐一排树。
Mirko 的伐木机工作流程如下：Mirko 设置一个高度参数 _H_（米），伐木机升起一个巨大的锯片到高度 _H_，并锯掉所有树比 H 高的部分（当然，树木不高于 H 米的部分保持不变）。Mirko 就得到树木被锯下的部分。例如，如果一排树的高度分别为 20,15,10 和 17，Mirko 把锯片升到 15 米的高度，切割后树木剩下的高度将是 15,15,10 和 15，而 Mirko 将从第 1 棵树得到 5 米，从第 4 棵树得到 2 米，共得到 7 米木材。
Mirko 非常关注生态保护，所以他不会砍掉过多的木材。这也是他尽可能高地设定伐木机锯片的原因。请帮助 Mirko 找到伐木机锯片的最大的整数高度 _H_，使得他能得到的木材至少为 M 米。换句话说，如果再升高 1 米，他将得不到 M 米木材。
我们可以在 $1$ 到 $10^9$ 中枚举答案，但是这种朴素写法肯定拿不到满分，因为从 $1$ 枚举到 $10^9$ 太耗时间。我们可以在 $[1, 10^9]$ 的区间上进行二分作为答案，然后检查各个答案的可行性（一般使用贪心法），这就是二分答案
int a[1000005];
int n, m;
bool check(int k) { // 检查可行性，k 为锯片高度
long long sum = 0;
for (int i = 1; i <= n; i++) // 检查每一棵树
if (a[i] > k) // 如果树高于锯片高度
sum += (long long)(a[i] - k); // 累加树木长度
return sum >= m; // 如果满足最少长度代表可行
}
int find() {
int l = 1, r = 1e9 + 1; // 因为是左闭右开的，所以 10^9 要加 1
while (l + 1 < r) { // 如果两点不相邻
int mid = (l + r) / 2; // 取中间值
if (check(mid)) // 如果可行
l = mid; // 升高锯片高度
else
r = mid; // 否则降低锯片高度
}
return l; // 返回左边值
}
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> a[i];
cout << find();
return 0;
}
三分法
三分法可以用来查找凸函数的最大（小）值。
- 如果
lmid和rmid在最大（小）值的同一侧：由于单调性，一定是二者中较大（小）的那个离最值近一些，较远的那个点对应的区间不可能包含最值，所以可以舍弃 - 如果在两侧：由于最值在二者中间，我们舍弃两侧的一个区间后，也不会影响最值，所以可以舍弃
代码实现
lmid = left + (right - left >> 1);
rmid = lmid + (right - lmid >> 1); // 对右侧区间取半
if (cal(lmid) > cal(rmid))
right = rmid;
else
left = lmid;
倍增
倍增法（Binary Lifting），顾名思义就是翻倍。它能够使线性的处理转化为对数级的处理，大大地优化时间复杂度。
这个方法在很多算法中均有应用，其中最常用的是 RMQ 问题和求 LCA（最近公共祖先）
例题1
如何用尽可能少的砝码称量出 $[0,31]$ 之间的所有重量？（只能在天平的一端放砝码）
答案是使用 1 2 4 8 16 这五个砝码，可以称量出 $[0,31]$ 之间的所有重量。同样，如果要称量 $[0,127]$ 之间的所有重量，可以使用 1 2 4 8 16 32 64 这七个砝码。每次我们都选择 2 的整次幂作砝码的重量，就可以使用极少的砝码个数量出任意我们所需要的重量
为什么说是极少呢？因为如果我们要量出 $[0,1023]$ 之间的所有重量，只需要 10 个砝码，需要量出 $[0,1048575]$ 之间的所有重量，只需要 20 个。如果我们的目标重量翻倍，砝码个数只需要增加 1。这叫“对数级”的增长速度，因为砝码的所需个数与目标重量的范围的对数成正比
例题2
给出一个长度为 $n$ 的环和一个常数 $k$ ，每次会从第 $i$ 个点跳到第 $(i+k) \mod n + 1$ 个点，总共跳了 $m$ 次。每个点都有一个权值，记为 $a_i$，求 $m$ 次跳跃的起点的权值之和对 $10^9 + 7$ 取模的结果
数据范围：$1 \le n \le 10^6 \ ,\ 1 \le m \le 10^{18} \ ,\ 1 \le k \le n \ ,\ 0 \le a_i \le 10^9$
这里显然不能暴力模拟跳 $m$ 次。因为 $m$ 最大可到 $10^18$ 级别，如果暴力模拟的话，时间承受不住
所以就需要进行一些预处理，提前整合一些信息，以便于在查询的时候更快得出结果。如果记录下来每一个可能的跳跃次数的结果的话，不论是时间还是空间都难以承受
那么应该如何预处理呢？看看第一道例题
回到本题，我们要预处理一些信息，然后用预处理的信息尽量快的整合出答案。同时预处理的信息也不能太多。所以可以预处理出以 2 的整次幂为单位的信息，这样的话在预处理的时候只需要处理少量信息，在整合的时候也不需要大费周章
在这题上，就是我们预处理出从每个点开始跳 1、2、4、8 等等步之后的结果（所处点和点权和），然后如果要跳 13 步，只需要跳 1+4+8 步就好了。也就是说先在起始点跳 1 步，然后再在跳了之后的终点跳 4 步，再接着跳 8 步，同时统计一下预先处理好的点权和，就可以知道跳 13 步的点权和了
对于每一个点开始的 $2^i$ 步，记录一个 go[i][x] 表示第 $x$ 个点跳 $2^i$ 步之后的终点，而 sum[i][x] 表示第 $x$ 个点跳 $2^i$ 步之后能获得的点权和。预处理的时候，开两重循环，对于跳 $2^i$ 步的信息，我们可以看作是先跳了 $2^{i-1}$ 步，再跳 $2^{i-1}$ 步，因为显然有 $2^{i-1} + 2^{i-1} = 2^i$。即我们有 sum[i][x] = sum[i-1][x]+sum[i-1][go[i-1][x]]，且 go[i][x] = go[i-1][go[i-1][x]]
当然还有一些实现细节需要注意。为了保证统计的时候不重不漏，我们一般预处理出“左闭右开”的点权和。亦即，对于跳 1 步的情况，我们只记录该点的点权和；对于跳 2 步的情况，我们只记录该点及其下一个点的点权和。相当于总是不将终点的点权和计入 sum。这样在预处理的时候，只需要将两部分的点权和直接相加就可以了，不需要担心第一段的终点和第二段的起点会被重复计算
这题的 $m \le 10^{18}$，虽然看似恐怖，但是实际上只需要预处理出 65 以内的 $i$，就可以轻松解决，比起暴力枚举快了很多。这个做法的时间复杂度是预处理 $O(n \log n)$，查询每次 $O(\log n)$
参考代码
#include <cstdio>
using namespace std;
const int mod = 1000000007;
int modadd(int a, int b) {
if (a + b >= mod) return a + b - mod; // 减法代替取模，加快运算
return a + b;
}
int vi[1000005];
int go[75][1000005]; // 将数组稍微开大以避免越界，小的一维尽量定义在前面
int sum[75][1000005];
int main() {
int n, k;
scanf("%d%d", &n, &k);
for (int i = 1; i <= n; ++i) {
scanf("%d", vi + i);
}
for (int i = 1; i <= n; ++i) {
go[0][i] = (i + k) % n + 1;
sum[0][i] = vi[i];
}
int logn = 31 - __builtin_clz(n); // 一个快捷的取对数的方法
for (int i = 1; i <= logn; ++i) {
for (int j = 1; j <= n; ++j) {
go[i][j] = go[i - 1][go[i - 1][j]];
sum[i][j] = modadd(sum[i - 1][j], sum[i - 1][go[i - 1][j]]);
}
}
long long m;
scanf("%lld", &m);
int ans = 0;
int curx = 1;
for (int i = 0; m; ++i) {
if (m & (1 << i)) { // 参见位运算的相关内容，意为 m 的第 i 位是否为 1
ans = modadd(ans, sum[i][curx]);
curx = go[i][curx];
m ^= 1ll << i; // 将第 i 位置零
}
}
printf("%d\n", ans);
}
构造
构造题是比赛中常见的一类题型
从形式上来看，问题的答案往往具有某种规律性，使得在问题规模迅速增大的时候，仍然有机会比较容易地得到答案
这要求解题时要思考问题规模增长对答案的影响，这种影响是否可以推广。例如，在设计动态规划方法的时候，要考虑从一个状态到后继状态的转移会造成什么影响
构造题一个很显著的特点就是高自由度，也就是说一道题的构造方式可能有很多种，但是会有一种较为简单的构造方式满足题意。看起来是放宽了要求，让题目变的简单了，但很多时候，正是这种高自由度导致题目没有明确思路而无从下手
构造题另一个特点就是形式灵活，变化多样。并不存在一个通用解法或套路可以解决所有构造题，甚至很难找出解题思路的共性
例题
下面将列举一些例题让你体会构造题的一些思想内涵，给予思路上的启发
例题1
Codeforces Round #384 (Div. 2) C.Vladik and fractions
构造一组 $x,y,z$，使得对于给定的 $n$ ，满足$\dfrac 1x + \dfrac 1y + \dfrac 1z = \dfrac 2n$
从样例二可以看出本题的构造方法。
显然 $n,n+1,n(n+1)$ 为一组合法解。特殊地，当 $n=1$ 时，无解，这是因为 $n+1$ 与 $n(n+1)$ 此时相等
至于构造思路是怎么产生的，大概就是观察样例加上一点点数感了吧。此题对于数学直觉较强的人来说并不难
例题2
Luogu P3599 Koishi Loves Construction
Task1：试判断能否构造并构造一个长度为 $n$ 的 $1\dots n$ 的排列，满足其 $n$ 个前缀和在模 $n$ 的意义下互不相同
Taks2：试判断能否构造并构造一个长度为 $n$ 的 $1\dots n$ 的排列，满足其 $n$ 个前缀积在模 $n$ 的意义下互不相同
对于 task1：
当 $n$ 为奇数时，无法构造出合法解
当 $n$ 为偶数时，可以构造一个形如 $n,1,n-2,3, \cdots$ 这样的数列
首先，我们可以发现 $n$ 必定出现在数列的第一位，否则 $n$ 出现前后的两个前缀和必然会陷入模意义下相等的尴尬境地
然后，我们考虑构造出整个序列的方式：
考虑通过构造前缀和序列的方式来获得原数列，可以发现前缀和序列两两之间的差在模意义下不能相等，因为前缀和序列的差分序列对应着原来的排列
因此我们尝试以前缀和数列在模意义下为 $0,1,-1,2,-2, \cdots$
这样的形式来构造这个序列，不难发现它完美地满足所有限制条件
对于 task2：
当 $n$ 为除 $4$ 以外的合数时，无法构造出合法解
当 $n$ 为质数或 $4$ 时，可以构造一个形如 $1,\dfrac 21, \dfrac 32, \cdots, \dfrac{n-1}{n-2},n$ 这样的数列
先考虑什么时候有解：
显然，当 $n$ 为合数时无解。因为对于一个合数来说，存在两个比它小的数 $p,q$ 使得 $p \times q \equiv 0 (\mod n)$，如 $(3 \times 6) % 9 \equiv 0$。那么，当 $p,q$ 均出现过后，数列的前缀积将一直为 $0$，故合数时无解。特殊地，我们可以发现 $4=2 \times 2$，无满足条件的 $p,q$，因此存在合法解
我们考虑如何构造这个数列：
和 task1 同样的思路，我们发现 $1$ 必定出现在数列的第一位，否则 $1$ 出现前后的两个前缀积必然相等；而 $n$ 必定出现在数列的最后一位，因为 $n$ 出现位置后的所有前缀积在模意义下都为 。手玩几组样例以后发现，所有样例中均有一组合法解满足前缀积在模意义下为$1,2,4,\cdots, n$ ，因此我们可以构造出上文所述的数列来满足这个条件。那么我们只需证明这 $n$ 个数互不相同即可。
我们发现这些数均为 $1\cdots n-2$的逆元 $+1$ ，因此各不相同，此题得解
