鸽巢原理，或称抽屉原理：把 n+1 个物体放进 n 个盒子，至少有一个盒子包含两个或更多的物体。 例如：1. 在 1500 个人中至少有 5 人生日相同； 2. n 个人互相握手，一定有两个人握手次数相同。

乘法快速幂  int fpow(int a, int n) { int res = 1; for(; n; n>>=1, a*=a) if(n&1) res*=a; return res; }矩阵快速幂 struct matrix { int m[10][10], n; matrix(int n, int k = 0): n(n){ for(int i = 1; i <= n; ++ i) { for(int j = 1; j <= n; ++ j) { if (i == j) m[i][j] = k; else m[i][j] = 0; } } } matri...

2 - SAT 问题: 有 n 个集合，其中一些处在不同集合的元素之间有限制关系，从 n 个集合中分别挑选一个元素组成序列，使其满足所有限制关系，判断序列是否存在，这就是 SAT 适定性（Satisfiability）问题。如果一个集合只有两个元素，则 2-SAT 问题。限制关系：A，B 不能同时选，则A，B 只能同时选，则A，B 必须选一个，则A 必须选，则

字典树（前缀树） 具体来说，Trie一般支持两个操作：  insert(S)：插入操作，就是将一个字符串 S 加入到集合中。 search(S)：查询操作，就是查询一个字符串 S 是不是在集合中。   int trie[maxn][26], tot; // 字典树 & 前缀树 int exist[maxn]; // 有多少字符串在此处结束 int num[maxn]; // 统计前缀个数 void insert(char s[]) { // 插入字典树 int pos = 0, n = strlen(s+1); for(int i = 1; i <= n; ++ i) { int...

manacher（马拉车）算法 时间复杂度 求解一个字符串的最长回文子串长度的问题。注：先插入 n+1 个 # ，再设置一个 po，维护已知区域 (po-Next[po]，po+Next[po])，即维护 po。  char s[maxn], t[maxn<<1]; // s 为文本串 t 为加 # 串 int Next[maxn<<1]; // t 中以 i 为中心的最长回文半径 int manacher(char s[]) { int n = strlen(s+1); for(int i = 1; i <= n+1; ++ i) { t[(i<<1...

KMP KMP 是单模匹配算法，即在一个长度为 n 的文本串中查找一个长度为 m 的模式串。  KMP 算法的基础 时间复杂度 在用 KMP 算法时，指向 s 的 i 指针不会回溯，而是一直往下走到底。那么 KMP 是如何让 i 不回溯，只回溯 j 的呢？这就是 KMP 的核心———fail[]数组。当出现失配后，进行下一次匹配时，用fail[]指出 j 的回溯的位置。注：维护一个最大前缀。注1：完善，fail 指针要标记到 m+1，在模式串第 m 位也匹配成功后仍然可以在 m+1 位进行回溯。注2：优化，当 t[i] = t[pos]，fail[i+1] 可以回溯到 pos+1，但当 t[i...

最近公共祖先 LCA（Least Common Ancestors），即最近公共祖先，指对于有根树 T 的两个结点 u 、v ，最近公共祖先 LCA(T,u,v) 表示一个结点 x, 满足 x 是 u、v 的祖先且 x 的深度尽可能大。   树上倍增 int anc[maxn][32]; // 结点 i 的第 2^j 个祖先 int depth[maxn]; // 深度 int dis[maxn]; // 距离 void dfs(int x, int fa, int d) { depth[x] = d; for(int i = head[x]; ~i; i = e[i].next) { int...

割点和割边 在无向图中，所有能互通的点组成了一个“连通分量”。在一个连通分量中有一些关键的点，如果删除它，会把这个连通分量分成两个或更多，这种点称为割点（cut vertex）。在一个连通分量中，如果删除一条边，把这个连通分量分成两个，这个边称为割边（cut eddge，又称为桥，bridge）。  深搜优先生成树  T 的根节点 s 是割点，当且仅当 s 有两个或更多的子结点。 T 的非根节点 u 是割点，当且仅当 u 存在一个子结点 v，v 及其后代都没有回退边连回 u 的祖先。  // 割点 vector<int> g[maxn]; int dfn[maxn], low[ma...

序列自动机 序列自动机是一个可以快速判断字符串t是否是字符串s的子序列的一个算法。  序列自动机基础  初始化：对s构造序列自动机，使用 代表从第i个位置开始，字符j出现的第一个位置。我们倒着遍历更新即可。  const int maxn = 1e6+1; const int inf = 0x3f3f3f3f; char s[maxn], t[maxn]; // 原串与子串 int Nxt[maxn][26]; // 序列自动机的存储 void init(int n) { // 序列自动机初始化 for(int i = 0; i < 26; ++ i) Nxt[n+1][i] = inf...

最小生成树 最小生成是无向图中的一个问题。  kruskal 算法 时间复杂度 ，m 为边的个数  对边进行排序。 用并查集处理连通性问题。  const int maxn = 1e6+1; struct E{ // 图中的边 int u, v, w; }e[maxn]; //struct edge{ // 最小生成树的边 // int to, w; // edge(){} // edge(int to, int w): to(to), w(w){} //}; vector<edge> g[maxn]; // 最小生成树边的存储 int f[maxn]; // 并查集-数组 int...

最短路径问题 在一个图中有 n 个点、m 条边。边有权值，例如费用、长度等，权值可正可负。边可能是有向的，也可能是无向的。给定两个点，起点是 s，终点是 t，在所有能连接 s 和 t 的路径中寻找边的权值之和最小的路径，这就是最短路径问题。注：若图中存在负圈，则不存在最短路问题，若存在负边权，则不能用 Dijkstra算法。  Floyd-Warshall 算法 算法复杂度：Floyd 用到了动态规划的思想：求两点 i、j 之间的最短距离，可以分两种情况考虑，即经过图中某个点 k 的路径和不经过点 k 的路径，取两者中的最短路径。注：有重边要在输入的时候更新最小值。 const int max...

容斥原理的基本概念 在计数时，必须注意没有重复，没有遗漏。为了使重叠部分不被重复计算，人们研究出一种新的计数方法，这种方法的基本思想是：先不考虑重叠的情况，把包含于某内容中的所有对象的数目先计算出来，然后再把计数时重复计算的数目排斥出去，使得计算的结果既无遗漏又无重复，这种计数的方法称为容斥原理.注：简单来说，就是奇加偶减。  容斥原理拓展  染色，一个圆分成 n 块，有 k 种颜色，相邻的两块颜色不能相同，有多少种涂色方式。公式： ，注： n = 1 需特判。  专题 https://nanti.jisuanke.com/t/A2000 【拓展.1】

全错位排列的基本概念 一个人写了n封不同的信及相应的n个不同的信封，他把这n封信都装错了信封，问都装错信封的装法有多少种？  数学公式 证明：设1，2，3，…，n的全排列 的集合为 S，而使 的群排列集合记为 ，所以 ，又因为 ，由容斥定理可得： ,化简得：  递推公式 图示：

群论的基本概念  群 G 是定义在一个二元组 （S，❈）的代数结构，S 代表一个集合，❈ 代表一种二元运算。满足下列条件的二元组才可称为群：封闭性：∀x,y ∈ S x ❈ y ∈ S结合律：∀x,y,z ∈ S (x ❈ y) ❈ z = x ❈ (y ❈ z)单位元：∃e ∈ S，∀x ∈ S e ❈ x = x ❈ e = x逆元：∀x ∈ S，∃y ∈ S x ❈ y = y ❈ x = e，记 y =   群的阶、元素的阶 群的阶：G 中所含元素的个数，称为群 G 的阶，记为 |G|，即 S 中所含元素的个数。若群 G 为无限群，则 |G| 为 +∞。元素的阶：在群 G 中，a ∈ ...