##简介后缀数组（Suffix Array, SA）是一种在字符串问题中很实用的工具，其主要作用是求多模板匹配和最长公共前缀（LCP）。与 AC自动机 预先处理模板串不同，后缀数组在进行多模板匹配的是预处理文本串。##模板后缀数组的构造方法主要有三个： 哈希、倍增、DC3。其中哈希是近似算法，方便写，虽然不能保证绝对正确但效果还是比较好的；哈希和DC3都是线性时间复杂度的，而倍增算法则是 $O(Mlog_2N) ,\text{M:字符集长度;N:串长}$ ,不过由于 DC3 难于理解，不太实用，本篇文章将不会涉及。###Hash比较好理解，不过写起来根倍增难度不相上下，而倍增可以保证绝对正确， ...

Polya 定理常在算法竞赛中用于解决计数问题。首先介绍一下理解此定理需要的数学基础：##1 群给定集合 $G={a,b,c,\dots}$ 和集合 $G$ 上的二元运算 $$ ，如果满足：运算 $$ 是封闭的且是可结合的；存在单位元 $e$ 和逆元（ $a$ 的逆元记为 $a^{-1}$ ），则称集合 $G$ 在运算 $$ 下是一个群，记为 $(G,)$ 。##2 置换群置换：集合 ${1,2,,\dots,n}$ 的一一映射成为一个一元置换，记为： $$\sigma=\begin{pmatrix}1 & 2 & \dots & n \\sigma(1) & ...

树链剖分适用于一些复杂的题目，可以较为充分获取树上的信息，将其转换为线性结构后可以很方便的使用线性数据结构进行处理。

这两天阴差阳错的研究了邹等周冬前辈的两篇论文～～##理论###图的关联矩阵对于无向图 $G$ ，我们定义它的关联矩阵 $B$ 是一个 $n\times m$ 的矩阵，并且满足：如果 $e_k=(v_i,v_j)$ ，那么 $B_{ik}$ 和 $B_{jk}$ 一个为 $1$ ，另一个为$-1$ ，而第 $k$ 列其它元素均为 $0$ 。 举例说明： 对于此图 $G$ ，其矩阵如下：$$\begin{bmatrix} 1 & -1 & 0 \[0.3em] -1 & 0 & -1 \[0.3em] 0 ...

##模型每个平面图 $G$ 都有一个与之对偶的平面图 $G^$$G^$ 有如下性质： $G^*$ 中的每个点对应 $G$ 中的一个面 对于 $G$ 中的，每条边 $e$ $e$ 属于两个面 $f_1,f_2$ ，加入边 $(f_1^,f_2^)$ $e$ 只属于一个面 $f$ ，加入回边 $(f^,f^)$ （图中加入了个绿色边围成的面，需要删除 $s^$ 与 $t^$ 之间的边） 这样我们通过求 $s^$ 到 $t^$ 的最短路，就可以求出原图中的最大流（最小割） 分析一下时间复杂度： 直接用 Dinic 求最大流： $O(EV^2)$ 最大流转化最短路，用堆优化 Dijk ...

##[NOI2002] 银河英雄传说 题目描述 公元五八〇一年，地球居民迁移至金牛座α第二行星，在那里发表银河联邦创立宣言，同年改元为宇宙历元年，并开始向银河系深处拓展。 宇宙历七九九年，银河系的两大军事集团在巴米利恩星域爆发战争。泰山压顶集团派宇宙舰队司令莱因哈特率领十万余艘战舰出征，气吞山河集团点名将杨威利组织麾下三万艘战舰迎敌。 杨威利擅长排兵布阵，巧妙运用各种战术屡次以少胜多，难免恣生骄气。在这次决战中，他将巴米利恩星域战场划分成 30000 列，每列依次编号为 $1, 2,\dots,30000$ 。之后，他把自己的战舰也依次编号为 $1, 2,\dots,30000$，让第i号战舰 ...

图论中最基础的算法是最短路，然而近些年在竞赛中已很少考最短路问题，许多图论题目往往是要求一种十分诡异的东西，这时候我们想直接求是不现实的，二分答案就应运而生了。##小奇回地球(earth) 题目背景 开学了，小奇在回地球的路上，遇到了一个棘手的问题。 问题描述 简单来说，它要从标号为 1 的星球到标号为 n 的星球，某一些星球之间有航线。由于超时空隧道的存在，从一个星球到另一个星球时间可能会倒流，而且，从星球 a 到 b 耗费的时间和星球 b 到 a 耗费的时间不一定相同。 宇宙法规定：“禁止在出发时间前到达目的地。”每艘飞船上都有速度调节装置，可以调节飞行的时间。其功能可以使得整次航程中所有 ...

##倍增法 在线算法 时间复杂度： 预处理：$O(N)$ 查询：$O(log_2N)$123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869#include<iostream>#include<cstdio>#include<cstring>#include<cmath>using namespace std;int m,n,q,anc[100 ...

FFT（快速傅里叶变换, Fast Fourier Transformation) 在算法竞赛中的主要应用是加速多项式运算。 以多项式乘法为例：朴素算法需要 $O(N^2)$ 的时间复杂度，而经过 FFT 优化后只需要 $O(Nlog_2N)$ 的时间复杂度。 数学基础FFT 作为一个数学算法，比起复杂的数据结构，其编程较为简单，但是它对于数学的要求比较高，要想理解此算法必须先有一定的数学基础。 多项式的表示多项式有两种表示方法： 系数表达法 点值表达法 其实有些像函数的表达，一二次函数为例，可以用解析式表示，也可以用 3 个以上的点来表示。 系数表达对于次数界为 $n$ 的多项式 $A( ...

##最大流###描述在图中，给出每条边的最大流，求出从一给定源点到汇点的最大流###算法单纯的贪心法由于搜索顺序会导致结果不同的问题并不能保证求出正确的答案，只需要将原始贪心算法中加入一个“反悔”机制就可以保证求出正确答案 实现中只需要加入反向边，没流过一条边，就将这条边的边权减去流量，并把反向边的边权加上这个流量 实际上就是通过加入反向边实现抵消操作####Ford-Fulkersondfs 时间复杂度：$O(FE)$####Edmonds-Karpbfs优化 时间复杂度：$O(E^2V)$####Dinic每次找一条路前，先通过一次bfs更新每个点的level，目的是在之后的dfs中优先遍 ...