51工具盒子做题步骤 {#做题步骤}
- 先分析它的时间复杂度
- 出题人想要考什么算法
- 写代码
- 写测试数据
刷题网站 {#刷题网站}
https://www.dotcpp.com/oj/lanqiao/
https://www.lanqiao.cn/problems/
时间复杂度 {#时间复杂度}
https://www.acwing.com/blog/content/32/
时间限制为1s时:
- n ≤ 30 => O(2 ^n^ ), dfs+剪枝，状态压缩dp
- n ≤ 100 => O(n ^3^ )，floyd，dp，高斯消元
- n ≤ 1000 => O(n ^2^ )，O(n ^2^ logn)，dp，二分，朴素版Dijkstra、朴素版Prim、Bellman-Ford
- n ≤ 10000 => O(n∗√n)，块状链表、分块、莫队
- n ≤ 100000 => O(nlogn) => 各种sort，线段树、树状数组、set/map、heap、拓扑排序、dijkstra+heap、prim+heap、Kruskal、spfa、求凸包、求半平面交、二分、CDQ分治、整体二分、后缀数组、树链剖分、动态树
- n ≤ 1000000 => O(n), 以及常数较小的 O(nlogn) 算法 => 单调队列、 hash、双指针扫描、并查集，kmp、AC自动机，常数比较小的 O(nlogn) 的做法：sort、树状数组、heap、dijkstra、spfa
- n ≤ 10000000 => O(n)，双指针扫描、kmp、AC自动机、线性筛素数
- n ≤ 10 ^9^ => O(√n)，判断质数
- n ≤ 10 ^18^ => O(logn)，最大公约数，快速幂，数位DP
- n ≤ 10 ^1000^ => O((logn) ^2^ )，高精度加减乘除
- n ≤ 10 ^100000^ => O(logk×loglogk)，k表示位数，高精度加减、FFT/NTT
快读快写 {#快读快写}
*
01
*
02
*
03
*
04
*
05
*
06
*
07
*
08
*
09
*
10
*
11
*
12
*
13
*
14
*
15
*
16
*
17
*
18
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
static StreamTokenizer cin = new StreamTokenizer(br);
public static int nextInt() throws Exception {
cin.nextToken();
return (int) cin.nval;
}
public static double nextDouble() throws Exception {
cin.nextToken();
return cin.nval;
}
//只能读字母
public static String next() throws Exception {
cin.nextToken();
return cin.sval;
}
</code>
</pre>
基础算法 {#基础算法}
------------
### 整数二分 {#整数二分}
[https://oi-wiki.org/basic/binary/#二分答案](https://oi-wiki.org/basic/binary/#%E4%BA%8C%E5%88%86%E7%AD%94%E6%A1%88)
````````````````````````````````prism language-java
static boolean check(int x) {/* ... */} // 检查x是否满足某种性质
// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用：
static int bsearch_1(int l, int r) {
while (l < r) {
int mid = (l + r) >>> 1;
if (check(mid)) r = mid; // check()判断mid是否满足性质
else l = mid + 1;
}
return l;
}
// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用：
static int bsearch_2(int l, int r) {
while (l < r) {
int mid = (l + r + 1) >>> 1;
if (check(mid)) l = mid;
else r = mid - 1;
}
return l;
}
</code>
</pre>
### 一维前缀和 {#一维前缀和}
[https://oi-wiki.org/basic/prefix-sum/#前缀和](https://oi-wiki.org/basic/prefix-sum/#%E5%89%8D%E7%BC%80%E5%92%8C)
S[i] = a[1] + a[2] + ... a[i]
a[l] + ... + a[r] = S[r] - S[l - 1]
</code>
</pre>
### 二维前缀和 {#二维前缀和}
S[i, j] = 第i行j列格子左上部分所有元素的和
以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵的和为：
S[x2, y2] - S[x1 - 1, y2] - S[x2, y1 - 1] + S[x1 - 1, y1 - 1]
</code>
</pre>
### 一维差分 {#一维差分}
给区间[l, r]中的每个数加上c：B[l] += c, B[r + 1] -= c
</code>
</pre>
### 二维差分 {#二维差分}
给以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵中的所有元素加上c：
S[x1, y1] += c, S[x2 + 1, y1] -= c, S[x1, y2 + 1] -= c, S[x2 + 1, y2 + 1] += c
</code>
</pre>
数据结构 {#数据结构}
------------
### 单调栈 {#单调栈}
<https://oi-wiki.org/ds/monotonous-stack/>
常见模型：找出每个数左边离它最近的比它大/小的数
```````````````````````````````prism language-java
int tt = 0;
int[] stk = new int[n + 1];
for (int i = 1; i <= n; i++) {
while (tt > 0 && check(stk[tt], i)) {
tt--;
}
stk[++tt] = i;
}
</code>
</pre>
### 单调队列 {#单调队列}
<https://oi-wiki.org/ds/monotonous-queue/>
常见模型：找出滑动窗口中的最大值/最小值
``````````````````````````````prism language-java
int hh = 0, tt = -1;
int[] q = new int[n];
for (int i = 0; i < n; i++) {
while (hh <= tt && check_out(q[hh])) {
hh++;
}
while (hh <= tt && check(q[tt], i)) {
tt--;
}
q[++tt] = i;
}
</code>
</pre>
### KMP {#kmp}
<https://oi-wiki.org/string/kmp/>
求模式串的Next数组：
`````````````````````````````prism language-java
int[] ne = new int[m + 1];
ne[1] = 0;
for (int i = 2, j = 0; i <= m; i++) {
while (j != 0 && p[i] != p[j + 1]) {
j = ne[j];
}
if (p[i] == p[j + 1]) {
j++;
}
ne[i] = j;
}
</code>
</pre>
匹配：
````````````````````````````prism language-java
for (int i = 1, j = 0; i <= n; i++) {
while (j != 0 && s[i] != p[j + 1]) {
j = ne[j];
}
if (s[i] == p[j + 1]) {
j++;
}
if (j == m) {
j = ne[j];
// 匹配成功后的逻辑
}
}
</code>
</pre>
### 并查集 {#并查集}
<https://oi-wiki.org/ds/dsu/>
```````````````````````````prism language-java
static int n;
static int[] p = new int[n + 1]; // 存储每个点的祖宗节点
// 返回x的祖宗节点
static int find(int x) {
if (p[x] != x) {
p[x] = find(p[x]);
}
return p[x];
}
// 初始化，假定节点编号是1~n
static void init() {
for (int i = 1; i <= n; i++) {
p[i] = i;
}
}
// 合并a和b所在的两个集合
static void union(int a, int b) {
p[find(a)] = find(b);
}
</code>
</pre>
### 线段树 {#线段树}
<https://oi-wiki.org/ds/seg/>
``````````````````````````prism language-java
static int[] a;
static int[] d;
// 通过子节点计算父节点
static int pushUp(int l, int r) {
// 计算父节点的值
// ...
}
static void build(int s, int t, int p) {
// 对 [s,t] 区间建立线段树,当前根的编号为 p
if (s == t) {
d[p] = a[s];
return;
}
int m = s + ((t - s) >> 1);
// 移位运算符的优先级小于加减法，所以加上括号
// 如果写成 (s + t) >> 1 可能会超出 int 范围
build(s, m, p * 2);
build(m + 1, t, p * 2 + 1);
// 递归对左右区间建树
d[p] = pushUp(d[p * 2], d[(p * 2) + 1]);
}
static int getRes(int l, int r, int s, int t, int p) {
// [l, r] 为查询区间, [s, t] 为当前节点包含的区间, p 为当前节点的编号
if (l <= s && t <= r) {
return d[p]; // 当前区间为询问区间的子集时直接返回当前区间的和
}
int m = s + ((t - s) >> 1), sum = 0;
int lv = 0, rv = 0; // 默认值
if (l <= m) {
lv = getRes(l, r, s, m, p * 2);
}
// 如果左儿子代表的区间 [s, m] 与询问区间有交集, 则递归查询左儿子
if (r > m) {
rv = getRes(l, r, m + 1, t, p * 2 + 1);
}
return pushUp(lv, rv);
}
</code>
</pre>
图论 {#图论}
--------
### 邻接矩阵 {#邻接矩阵}
[https://oi-wiki.org/graph/save/#邻接矩阵](https://oi-wiki.org/graph/save/#%E9%82%BB%E6%8E%A5%E7%9F%A9%E9%98%B5)
`````````````````````````prism language-java
static int n;
static int[][] g = new int[n + 1][n + 1]; // 存储边a->b
// 添加一条边a->b
static void add(int a, int b) {
g[a][b] = 1;
}
</code>
</pre>
### 邻接表 {#邻接表}
[https://oi-wiki.org/graph/save/#邻接矩阵](https://oi-wiki.org/graph/save/#%E9%82%BB%E6%8E%A5%E7%9F%A9%E9%98%B5)
````````````````````````prism language-java
//n个点，m条单向边
static int[] h = new int[n + 1]; // 存储每个点的单链表的头结点
static int[] e = new int[m + 1]; // 存储每个点的可达点
static int[] ne = new int[m + 1]; // 存储每个点的下一个可达点
static int idx;
// 添加一条边a->b
static void add(int a, int b) {
e[idx] = b;
ne[idx] = h[a];
h[a] = idx++;
}
// 初始化
static void init() {
Arrays.fill(h, -1);
}
</code>
</pre>
### 深度优先遍历 {#深度优先遍历}
<https://oi-wiki.org/graph/dfs/>
```````````````````````prism language-java
static int n,m;
static boolean[] st = new boolean[n + 1]; // 表示点是否被遍历过
static int[] h = new int[n + 1], e = new int[m + 1], ne = new int[m + 1];
static void dfs(int u) {
st[u] = true; // 表示点u已经被遍历过
for (int i = h[u]; i != -1; i = ne[i]) {
int j = e[i];
if (!st[j]) {
dfs(j);
}
}
}
</code>
</pre>
### 宽度优先遍历 {#宽度优先遍历}
<https://oi-wiki.org/graph/bfs/>
``````````````````````prism language-java
Queue<Integer> q = new LinkedList<>();
boolean[] st = new boolean[n + 1]; // 表示点是否被遍历过
st\[1\] = true; // 表示1号点已经被遍历过
q.offer(1);
while (!q.isEmpty()) {
int t = q.poll();
for (int i = h[t]; i != -1; i = ne[i]) {
int j = e[i];
if (!st[j]) {
st[j] = true; // 表示点j已经被遍历过
q.offer(j);
}
}
}
</code>
</pre>
### 拓扑排序 {#拓扑排序}
<https://oi-wiki.org/graph/topo/>
`````````````````````prism language-java
//n 表示点数
Queue<Integer> q = new LinkedList<>(); // 存储拓扑序列
int[] d = new int[n + 1]; // 存储点的入度
// 统计每个点的入度
for (int i = 1; i \<= n; i++) {
for (int j = h\[i\]; j != -1; j = ne\[j\]) {
int k = e\[j\];
d\[k\]++;
}
}
// 将入度为0的点入队
for (int i = 1; i \<= n; i++) {
if (d\[i\] == 0) {
q.offer(i);
}
}
while (!q.isEmpty()) {
int t = q.poll();
for (int i = h[t]; i != -1; i = ne[i]) {
int j = e[i];
if (--d[j] == 0) {
q.offer(j);
}
}
}
// 如果所有点都入队了，说明存在拓扑序列；否则不存在拓扑序列。
boolean hasTopologicalOrder = (tt == n - 1);
</code>
</pre>
### 朴素Dijkstra算法 {#朴素dijkstra算法}
时间复杂度：O(n\^2 + m), 其中 n 表示点数，m 表示边数
[https://oi-wiki.org/graph/shortest-path/#dijkstra-算法](https://oi-wiki.org/graph/shortest-path/#dijkstra-%E7%AE%97%E6%B3%95)
````````````````````prism language-java
static int n;
static int[][] g = new int[n + 1][n + 1]; // 存储每条边
static int[] dist = new int[n + 1]; // 存储1号点到每个点的最短距离
static boolean[] st = new boolean[n + 1]; // 存储每个点的最短路是否已经确定
// 求1号点到n号点的最短路，如果不存在则返回-1
static int dijkstra() {
Arrays.fill(dist, 0x3f3f3f3f);
dist[1] = 0;
for (int i = 0; i < n - 1; i++) {
int t = -1; // 在还未确定最短路的点中，寻找距离最小的点
for (int j = 1; j <= n; j++) {
if (!st[j] && (t == -1 || dist[t] > dist[j])) {
t = j;
}
}
// 用t更新其他点的距离
for (int j = 1; j <= n; j++) {
dist[j] = Math.min(dist[j], dist[t] + g[t][j]);
}
st[t] = true;
}
if (dist[n] == 0x3f3f3f3f) {
return -1;
}
return dist[n];
}
</code>
</pre>
### SPFA算法（队列优化的Bellman-Ford算法） {#spfa算法（队列优化的bellman-ford算法）}
时间复杂度：平均情况下 O(m), 最坏情况下 O(nm), 其中 n 表示点数，m 表示边数
[https://oi-wiki.org/graph/shortest-path/#队列优化spfa](https://oi-wiki.org/graph/shortest-path/#%E9%98%9F%E5%88%97%E4%BC%98%E5%8C%96spfa)
```````````````````prism language-java
static int n, m; // 总点数, 总边数
static int[] h = new int[n + 1];
static int[] w = new int[m + 1];
static int[] e = new int[m + 1];
static int[] ne = new int[m + 1];
static int[] dist = new int[n + 1]; // 存储每个点到1号点的最短距离
static boolean[] st = new boolean[n + 1]; // 存储每个点是否在队列中
// 求1号点到n号点的最短路距离，如果从1号点无法走到n号点则返回-1
static int spfa() {
Arrays.fill(dist, Integer.MAX_VALUE);
dist[1] = 0;
Queue<Integer> q = new LinkedList<>();
q.offer(1);
st[1] = true;
while (!q.isEmpty()) {
int t = q.poll();
st[t] = false;
for (int i = h[t]; i != -1; i = ne[i]) {
int j = e[i];
if (dist[j] > dist[t] + w[i]) {
dist[j] = dist[t] + w[i];
if (!st[j]) { // 如果队列中已存在j，则不需要将j重复插入
q.offer(j);
st[j] = true;
}
}
}
}
if (dist[n] == Integer.MAX_VALUE) {
return -1;
}
return dist[n];
}
</code>
</pre>
### SPFA判断图中是否存在负环 {#spfa判断图中是否存在负环}
时间复杂度：O(nm), 其中 n 表示点数，m 表示边数
``````````````````prism language-java
static int n, m; // 总点数, 总边数
static int[] h = new int[n + 1];
static int[] w = new int[m + 1];
static int[] e = new int[m + 1];
static int[] ne = new int[m + 1];
static int[] dist = new int[n + 1]; // dist[x]存储1号点到x的最短距离
static int[] cnt = new int[n + 1]; // cnt[x]存储1到x的最短路中经过的点数
static boolean[] st = new boolean[n + 1]; // 存储每个点是否在队列中
// 如果存在负环，则返回true，否则返回false。
static boolean spfa() {
Queue<Integer> q = new LinkedList<>();
for (int i = 1; i <= n; i++) {
q.offer(i);
st[i] = true;
}
while (!q.isEmpty()) {
int t = q.poll();
st[t] = false;
for (int i = h[t]; i != -1; i = ne[i]) {
int j = e[i];
if (dist[j] > dist[t] + w[i]) {
dist[j] = dist[t] + w[i];
cnt[j] = cnt[t] + 1;
if (cnt[j] >= n) { // 如果从1号点到x的最短路中包含至少n个点（不包括自己），则说明存在环
return true;
}
if (!st[j]) {
q.offer(j);
st[j] = true;
}
}
}
}
return false;
}
</code>
</pre>
### Floyd算法 {#floyd算法}
时间复杂度：O(n\^3), 其中 n 表示点数
[https://oi-wiki.org/graph/shortest-path/#floyd-算法](https://oi-wiki.org/graph/shortest-path/#floyd-%E7%AE%97%E6%B3%95)
`````````````````prism language-java
static final int INF = 0x3f3f3f3f;
static int n; // 总点数
static int[][] d = new int[n + 1][n + 1]; // 存储最短距离
// 初始化
static void init() {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (i == j) {
d[i][j] = 0;
} else {
d[i][j] = INF;
}
}
}
}
// 算法结束后，d[a][b]表示a到b的最短距离
static void floyd() {
for (int k = 1; k <= n; k++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
d[i][j] = Math.min(d[i][j], d[i][k] + d[k][j]);
}
}
}
}
</code>
</pre>
### 朴素版Prim算法 {#朴素版prim算法}
时间复杂度：O(n\^2 + m), 其中 n 表示点数，m 表示边数
[https://oi-wiki.org/graph/mst/#prim-算法](https://oi-wiki.org/graph/mst/#prim-%E7%AE%97%E6%B3%95)
````````````````prism language-java
static final int INF = 0x3f3f3f3f;
static int n; // n表示点数
static int[][] g = new int[n + 1][n + 1]; // 邻接矩阵，存储所有边
static int[] dist = new int[n + 1]; //
// 存储其他点到当前最小生成树的距离
static boolean[] st = new boolean[n + 1]; // 存储每个点是否已经在生成树中
// 如果图不连通，则返回INF(值是0x3f3f3f3f)，否则返回最小生成树的树边权重之和
static int prim() {
Arrays.fill(dist, INF);
int res = 0;
for (int i = 0; i < n; i++) {
int t = -1;
for (int j = 1; j <= n; j++) {
if (!st[j] && (t == -1 || dist[t] > dist[j])) {
t = j;
}
}
if (i != 0 && dist[t] == INF) {
return INF;
}
if (i != 0) {
res += dist[t];
}
st[t] = true;
for (int j = 1; j <= n; j++) {
dist[j] = Math.min(dist[j], g[t][j]);
}
}
return res;
}
</code>
</pre>
### Kruskal 算法 {#kruskal-算法}
时间复杂度：O(m \* log(m)), 其中 n 表示点数，m 表示边数
[https://oi-wiki.org/graph/mst/#kruskal-算法](https://oi-wiki.org/graph/mst/#kruskal-%E7%AE%97%E6%B3%95)
```````````````prism language-java
static int n, m; // n是点数，m是边数
static int[] p = new int[n + 1];
static int[][] e = new int[m + 1][3];
public static int find(int x) { // 并查集核心操作
if (p[x] != x) {
p[x] = find(p[x]);
}
return p[x];
}
public static int kruskal() {
Arrays.sort(e, 0, m, (o1, o2) -> o1[2] - o2[2]);
for (int i = 1; i <= n; i++) {
p[i] = i; // 初始化并查集
}
int res = 0, cnt = 0;
for (int i = 0; i < m; i++) {
int a = e[i][0], b = e[i][1], w = e[i][2];
a = find(a);
b = find(b);
if (a != b) { // 如果两个连通块不连通，则将这两个连通块合并
p[a] = b;
res += w;
cnt++;
}
}
//没有最小生成树
if (cnt < n - 1) {
return Integer.MAX_VALUE;
}
return res;
}
</code>
</pre>
数学知识 {#数学知识}
------------
### 试除法判定质数 {#试除法判定质数}
``````````````prism language-java
static boolean isPrime(int x) {
if (x < 2) return false;
for (int i = 2; i <= x / i; i++) {
if (x % i == 0) {
return false;
}
}
return true;
}
</code>
</pre>
### 试除法分解质因数 {#试除法分解质因数}
`````````````prism language-java
static void divide(int x) {
for (int i = 2; i <= x / i; i++) {
if (x % i == 0) {
int s = 0;
while (x % i == 0) {
x /= i;
s++;
}
System.out.println(i + " " + s);
}
}
if (x > 1) {
System.out.println(x + " " + 1);
}
System.out.println();
}
</code>
</pre>
### 线性筛法求素数 {#线性筛法求素数}
[https://oi-wiki.org/math/number-theory/sieve/#素数筛法](https://oi-wiki.org/math/number-theory/sieve/#%E7%B4%A0%E6%95%B0%E7%AD%9B%E6%B3%95)
````````````prism language-java
static int n;//求小于等于n的素数
static int[] primes = new int[n + 1]; // 存储所有素数
static boolean[] st = new boolean[n + 1]; // 存储x是否被筛掉
static int cnt = 0;
static void getPrimes(int n) {
for (int i = 2; i <= n; i++) {
if (!st[i]) {
primes[cnt++] = i;
}
for (int j = 0; j < cnt && primes[j] <= n / i; j++) {
st[primes[j] * i] = true;
if (i % primes[j] == 0) {
break;
}
}
}
}
</code>
</pre>
### 试除法求所有约数 {#试除法求所有约数}
```````````prism language-java
static List<Integer> getDivisors(int x) {
List<Integer> res = new ArrayList<>();
for (int i = 1; i <= x / i; i++) {
if (x % i == 0) {
res.add(i);
if (i != x / i) {
res.add(x / i);
}
}
}
Collections.sort(res);
return res;
}
</code>
</pre>
### 约数个数和约数之和 {#约数个数和约数之和}
如果 N = p1\^c1 \* p2\^c2 \* ... \* pk\^ck \*
约数个数： (c1 + 1) \* (c2 + 1) \* ... \* (ck + 1) \*
约数之和： (p1\^0 + p1\^1 + ... + p1\^c1) \* ... \* (pk\^0 + pk\^1 + ... + pk\^ck)
### 欧几里得算法 {#欧几里得算法}
求最大公因数
[https://oi-wiki.org/math/number-theory/gcd/#欧几里得算法](https://oi-wiki.org/math/number-theory/gcd/#%E6%AC%A7%E5%87%A0%E9%87%8C%E5%BE%97%E7%AE%97%E6%B3%95)
``````````prism language-java
static int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
</code>
</pre>
### 求欧拉函数 {#求欧拉函数}
欧拉函数，即 \varphi(n) ，表示的是小于等于 n 和 n 互质的数的个数。
<https://oi-wiki.org/math/number-theory/euler/>
`````````prism language-java
static int phi(int x) {
int res = x;
for (int i = 2; i <= x / i; i++) {
if (x % i == 0) {
res = res / i * (i - 1);
while (x % i == 0) {
x /= i;
}
}
}
if (x > 1) {
res = res / x * (x - 1);
}
return res;
}
</code>
</pre>
### 筛法求欧拉函数 {#筛法求欧拉函数}
[https://oi-wiki.org/math/number-theory/sieve/#筛法求欧拉函数](https://oi-wiki.org/math/number-theory/sieve/#%E7%AD%9B%E6%B3%95%E6%B1%82%E6%AC%A7%E6%8B%89%E5%87%BD%E6%95%B0)
````````prism language-java
static int n;
static int[] primes = new int[n + 1]; // 存储所有素数
static int[] euler = new int[n + 1]; // 存储每个数的欧拉函数
static boolean[] st = new boolean[n + 1]; // 存储x是否被筛掉
static int cnt; // 存储素数的个数
static void getEulers(int n) {
euler[1] = 1;
for (int i = 2; i <= n; i++) {
if (!st[i]) {
primes[cnt++] = i;
euler[i] = i - 1;
}
for (int j = 0; j < cnt && primes[j] <= n / i; j++) {
int t = primes[j] * i;
st[t] = true;
if (i % primes[j] == 0) {
euler[t] = euler[i] * primes[j];
break;
}
euler[t] = euler[i] * (primes[j] - 1);
}
}
}
</code>
</pre>
### 快速幂 {#快速幂}
求 m\^k mod p，时间复杂度 O(log(k))。
qmi(m, p - 2, p) 等于m模p下的乘法逆元
<https://oi-wiki.org/math/binary-exponentiation/>
```````prism language-java
static int qmi(int m, int k, int p) {
int res = 1 % p;
int t = m;
while (k != 0) {
if ((k & 1) == 1) {
res = res * t % p;
}
t = t * t % p;
k >>>= 1;
}
return res;
}
</code>
</pre>
### 扩展欧几里得算法 {#扩展欧几里得算法}
求x, y，使得ax + by = gcd(a, b)
若exgcd(a, b, x, y) == 1 则 (x\[0\]%b+b)%b 是a模b下的乘法逆元
[https://oi-wiki.org/math/number-theory/gcd/#扩展欧几里得算法](https://oi-wiki.org/math/number-theory/gcd/#%E6%89%A9%E5%B1%95%E6%AC%A7%E5%87%A0%E9%87%8C%E5%BE%97%E7%AE%97%E6%B3%95)
``````prism language-java
static int exgcd(int a, int b, int[] x, int[] y) {
if (b == 0) {
x[0] = 1;
y[0] = 0;
return a;
}
int d = exgcd(b, a % b, y, x);
y[0] -= (a/b) * x[0];
return d;
}
</code>
</pre>
### 线性求乘法逆元 {#线性求乘法逆元}
<https://oi-wiki.org/math/number-theory/inverse/>
`````prism language-java
static int n, p;
static long[] inv = new long[n + 1];
static void get() {
inv[1] = 1;
for (int i = 2; i <= n; ++i) {
inv[i] = (long)(p - p / i) * inv[p % i] % p;
}g
}
</code>
</pre>
贪心 {#贪心}
--------
<https://oi-wiki.org/basic/greedy/>
每一步行动总是按某种指标选取最优的操作。
动态规划 {#动态规划}
------------
### 分析法 {#分析法}
````prism language-mermaid
graph LR
A\[定义问题\] --\> B\[确定子问题\]
B --\> C\[确定状态\]
C --\> D\[确定状态转移方程\]
D --\> E\[确定初始条件和边界条件\]
E --\> F\[计算最优解\]
F --\> G\[返回最优解\]
</code>
</pre>
### 闫氏dp分析法 {#闫氏dp分析法}
<https://www.acwing.com/file_system/file/content/whole/index/content/1084122/>
```prism language-mermaid
graph LR
A\[问题\] --\> B\[状态表示\]
B --\> C\[集合\]
B --\> D\[属性\]
A --\> E\[状态计算\]
</code>
</pre>
内容参考 {#内容参考}
------------
<https://oi-wiki.org>
<https://www.acwing.com/activity/content/introduction/11/>
```
````
`````
``````
```````
````````
`````````
``````````
```````````
````````````
`````````````
``````````````
```````````````
````````````````
`````````````````
``````````````````
```````````````````
````````````````````
`````````````````````
``````````````````````
```````````````````````
````````````````````````
`````````````````````````
``````````````````````````
```````````````````````````
````````````````````````````
`````````````````````````````
``````````````````````````````
```````````````````````````````
````````````````````````````````
