Loading... 好久没更新了，上了大学一直忙，放寒假抽出空来总结一下学过的算法。 --- ## 目录 - 图、搜索 1. 图论入门 2. 搜索入门 3. 基础剪枝 4. 宽度优先搜索 5. 搜索综合应用 6. 图论基础（最短路，最小生成树，并查集） 7. 图论综合应用 - 动态规划 8. 线性DP 9. 背包问题1 10. 背包问题2 11. 区间DP 12. 树形DP 13. DP综合1 14. DP综合2 - 数据结构 15. ST表 16. 堆 17. 树状数组 18. 线段树 19. Hash 20. KMP算法 21. Trie树 - 数学 22. 质数 23. 快速幂 24. 约数 25. 矩阵乘法 26. 同余 27. 同余 28. 同余 ## 第一节 图论入门 ### 图论概念 **图论 (Graph theory)** 是数学的一个分支，图是图论的主要研究对象。 **图 (Graph)** 是由若干给定的顶点及连接两顶点的边所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系。顶点用于代表事物，连接两顶点的边则用于表示两个事物间具有这种关系。 ### 一、图论相关概念 #### 1. 图 - 由点和边组成的几何模型。。。 - 有向图、无向图、混合图。。。 - 有向边、无向边、边权 #### 2. 相邻 - 若存在一条边连接u，e则说u和e相邻 #### 3. 度数 - 一个点所连接边的个数。 **自环贡献两个度** - 度数为一，叶结点 - 度数为偶数，偶点 - 度数为奇数，奇点 ##### 有向图 - 出度 - 入度 #### 4. 简单图 - 自环：自己连向自己 - 重边：两条连接相同端点的边 - 简单图：无自环、重边的图 - 多重图：存在自环或重边的图 #### 5. 路径 - **路径 (Path)**：一条点和边组成的集合，并且点和边均没有重复。 - **环/圈 (Cycle)**：对于一个路径 ，若只有唯一重复出现的点对，则称是一个环。 #### 6. 连通 ##### 无向图 - 对于任意两个点，都至少存在一条路径 ##### 有向图 - 强连通：对于任意两个点u，v，都有一条路径从u到v并且有一条路径从v到u。 - 弱连通：把所有边替换成无向边后是无向连通图。 ### 二、如何存图 #### 1. 邻接矩阵 ##### 理论 - 开一个二维数组e，如果x到y有一条边，$e[x][y]=1$，如果是带权图，x到y的边权为w，只需$e[x][y] = w$。 ##### 实现 ```cpp #include<bits/stdc++.h> using namespace std; const int N = 5009; int e[N][N]; int main() { int n, m; scanf("%d%d", &n, &m); for(int i = 1; i <= m; i++) { int x, y, w; scanf("%d%d%d", &x, &y, &w); e[x][y] = w; e[y][x] = w; //如果是无向图就反向建立一条边 } return 0; } ``` ##### 复杂度 - 查询：$O(1)$ - 遍历一个点所有出边：$O(n)$ - 空间复杂度：$O(n^2)$ #### 2. 邻接表 ##### 原理 用一个支持动态增加空间的数组（vector）存储边。 ##### 实现 ```cpp #include<bits/stdc++.h> using namespace std; const int N = 5009; vector<int> e[N]; int main() { int n, m; scanf("%d%d", &n, &m); for(int i = 1; i <= m; i++) { int x, y, w; scanf("%d%d%d", &x, &y, &w); e[x].push_back(y); e[y].push_back(x) //如果是无向图就反向建立一条边 } return 0; } ``` ##### 复杂度 - 查询：$O(出边数)$ - 遍历x所有出边：同上 - 空间：$O(m)$ #### 3. 链式前向星 和邻接表差不多，使用链表实现。 ```cpp #include<bits/stdc++.h> using namespace std; const int N = 5009; struct Edge { int to, nxt, v; }e[N * 4]; int head[N], tot; void addEdge(int x, int y, int val) { e[++tot].to = y; e[tot].v = val; e[tot].nxt = head[x]; head[x] = tot; } int main() { int n, m; scanf("%d%d", &n, &m); for(int i = 1; i <= m; i++) { int x, y, w; scanf("%d%d%d", &x, &y, &w); addEdge(x, y, w); addEdge(y, x, w); //如果是无向图就反向建立一条边 } return 0; } ``` #### 图的遍历（图的dfs） - 常用链式前向星 - 例题https://oj.czos.cn/p/2052 ### 树的概念 #### 1. 定义 #### 2. 有关定义 - 森林 - 深度 - 叶子结点 #### 3. 有根树定义 - 根结点 - 叶子结点 - 父亲 - 祖先 - 兄弟 - 儿子 #### 4. 树的存储 - 邻接表、链式前向星 - 对于一个二叉树，可以如下保存 1. 对于节点x，其左儿子为$x\times2$，右儿子为$x\times2+1$。 ### 作业 - http://ybt.ssoier.cn:8088/problem_show.php?pid=1341 - http://ybt.ssoier.cn:8088/problem_show.php?pid=1374 - http://ybt.ssoier.cn:8088/problem_show.php?pid=1375 --- ## 第二节 搜索入门 ### 一、深度优先搜索（dfs） - 在 **搜索算法** 中，dfs常常指利用递归函数方便地实现暴力枚举的算法。 #### 导入 - 把正整数x分解为3个不同的正整数，如$6=1+2+3$，排在后面的数必须大于等于前面的数，输出所有方案。 ```cpp for (int i = 1; i <= n; ++i) for (int j = i; j <= n; ++j) for (int k = j; k <= n; ++k) if (i + j + k == n) printf("%d = %d + %d + %d\n", n, i, j, k); ``` - 接下来讲dfs方法 #### 概念 - 什么是递归？ - 回溯！！！ - 画出搜索树，手动模拟 - 注意终止条件 #### 例题 - http://ybt.ssoier.cn:8088/problem_show.php?pid=1317 - http://ybt.ssoier.cn:8088/problem_show.php?pid=1318 - http://ybt.ssoier.cn:8088/problem_show.php?pid=1213（八皇后，重点） - http://ybt.ssoier.cn:8088/problem_show.php?pid=1215（地图上的dfs，一类典型） - https://oj.czos.cn/p/1383 #### 作业 - http://ybt.ssoier.cn:8088/problem_show.php?pid=1214 - http://ybt.ssoier.cn:8088/problem_show.php?pid=1218 - http://ybt.ssoier.cn:8088/problem_show.php?pid=1219 - https://oj.czos.cn/p/1541 - http://ybt.ssoier.cn:8088/problem_show.php?pid=1216 - http://ybt.ssoier.cn:8088/problem_show.php?pid=1220 - https://oj.czos.cn/p/1381 - https://oj.czos.cn/p/1913 - https://oj.czos.cn/p/1441 - https://oj.czos.cn/p/1914 --- ## 第三节 基础剪枝 ### 一、剪枝概念 - 减小搜索树规模 - 尽早排除不必要分枝 ### 二、常见剪枝技巧 1. 优化搜索顺序 2. 排除等效冗余 3. 可行性剪枝：远远看到最后是个死胡同，尽早离开这个分支。 4. 最优性剪枝：如果当前情况比我们已经有的状态更差，不再继续往下走。 5. 记忆化（DP的另一种形式） ### 例题 - http://ybt.ssoier.cn:8088/problem_show.php?pid=1442（方法1，2） - http://ybt.ssoier.cn:8088/problem_show.php?pid=1441（上下界剪枝，1，3，4） - http://ybt.ssoier.cn:8088/problem_show.php?pid=1443 ### 作业 - http://ybt.ssoier.cn:8088/problem_show.php?pid=1444 - http://ybt.ssoier.cn:8088/problem_show.php?pid=1445 - http://ybt.ssoier.cn:8088/problem_show.php?pid=1446 - http://ybt.ssoier.cn:8088/problem_show.php?pid=1447 - https://www.luogu.com.cn/problem/P1312（！） --- ## 第四节 宽度优先搜索（BFS） ### 简介 在第二节中，我们有定义了深度优先搜索过程产生的搜索树结构，如果我们把问题状态空间类比为一张图，那么广度优先搜索，就相当于对这张图的广度优先遍历。我们用一个队列来实现广度优先搜索，起初队列中只包含初始状态，在bfs的过程中，我们不断从队头取出状态，对于该状态面临的所有分支，把沿着每条分支到达的下一个状态插入队尾。重复执行直到队列为空。 - 与dfs的区别 - 为什么比dfs高效 - 在DAG上的最短路 - 在地图上跑bfs的优点 ### 概念 1. 广搜模版 2. 例题画队列手动模拟 3. 注意一个节点（状态）入队一次，出队一次。 ### 注意 - 对于走地图游戏，尽量采用方向数组法（1， 0， -1， 0） ```cpp bfs(s) { q = new queue() q.push(s), visited[s] = true while (!q.empty()) { u = q.pop() for each edge(u, v) { if (!visited[v]) { q.push(v) visited[v] = true } } } } ``` ### 例题 - http://ybt.ssoier.cn:8088/problem_show.php?pid=1329 - http://ybt.ssoier.cn:8088/problem_show.php?pid=1330 - http://ybt.ssoier.cn:8088/problem_show.php?pid=1248（地图上跑bfs） - http://ybt.ssoier.cn:8088/problem_show.php?pid=1251 - http://ybt.ssoier.cn:8088/problem_show.php?pid=1250 ### 作业 - http://ybt.ssoier.cn:8088/problem_show.php?pid=1252 - http://ybt.ssoier.cn:8088/problem_show.php?pid=1253 - https://oj.czos.cn/p/1897 - https://oj.czos.cn/p/1434 - https://oj.czos.cn/p/1443 - http://ybt.ssoier.cn:8088/problem_show.php?pid=1255 - http://ybt.ssoier.cn:8088/problem_show.php?pid=1254 - http://ybt.ssoier.cn:8088/problem_show.php?pid=1256 - https://oj.czos.cn/p/1803 - https://oj.czos.cn/p/1444 - https://www.luogu.com.cn/problem/P1032 --- ## 第五节 搜索综合应用 ### 一、迭代加深 #### 基本思想 深搜是对于每一个分支走到底才回头，如果1搜索树深度很大，答案在较浅的节点上，开始选错节点会导致时间上升，因此加一个限制条件limit，每次搜索只搜到limit层不管有没有得到答案都不继续向下。搜完没有得到答案再适当增加limit再搜索。 了解即可，不做要求 ### 二、广搜优化 #### 1. 双端队列优化bfs - 例http://ybt.ssoier.cn:8088/problem_show.php?pid=1448 #### 2. Hash优化bfs - 例http://ybt.ssoier.cn:8088/problem_show.php?pid=1449 #### 3. 双向搜索（dfs，bfs） 从起始状态搜到终点状态是$O(2^n)$，如果从起点开始同时从终点开始，复杂度只有$O(2^{\frac{n}{2}})$ - 例http://ybt.ssoier.cn:8088/problem_show.php?pid=1450 ### 作业 - http://ybt.ssoier.cn:8088/problem_show.php?pid=1451 - http://ybt.ssoier.cn:8088/problem_show.php?pid=1452 - http://ybt.ssoier.cn:8088/problem_show.php?pid=1453 - http://ybt.ssoier.cn:8088/problem_show.php?pid=1454 - https://oj.czos.cn/p/1379 - https://oj.czos.cn/p/1850 - https://oj.czos.cn/p/1439 - https://oj.czos.cn/p/1823 --- ## 第六节 图论基础 ### 一、最短路 #### 概念 #### 算法 ##### SPFA - 队列优化 - 判断负环 ##### 更多优化 - Dijkstra（常用，单源） - Prim - Floyd（多源最短路） Dijkstra模版 ```cpp #include<cstdio> #include<queue> #include<cstring> using namespace std; typedef long long ll; const ll INF = 0x3f3f3f3f3f3f3f3f; const int N = 100009; int n, m, s; struct Edge{ int to, nxt; ll w; }e[2 * N]; int head[N], tot; bool vis[N]; ll dis[N]; void add(int x, int y, ll w){ e[++tot].to = y; e[tot].w = w; e[tot].nxt = head[x]; head[x] = tot; } void dijkstra(int st){ priority_queue<pair<ll, int> > pq; memset(vis, 0, sizeof(0)); memset(dis, 0x3f, sizeof(dis)); dis[st] = 0; pq.push(make_pair(-dis[st], st)); while(!pq.empty()){ int x = pq.top().second; pq.pop(); if(vis[x]) continue; vis[x] = 1; for(int i = head[x]; i; i = e[i].nxt){ int y = e[i].to; ll w = e[i].w; if(dis[y] > dis[x] + w){ dis[y] = dis[x] + w; pq.push(make_pair(-dis[y], y)); } } } } int main(){ scanf("%d%d%d", &n, &m, &s); for(int i = 1; i <= m; i++){ int x, y; ll w; scanf("%d%d%lld", &x, &y, &w); add(x, y, w); } dijkstra(s); for(int i = 1; i <= n; i++){ printf("%lld ", dis[i] == INF ? -1 : dis[i]); } return 0; } ``` SPFA模版 ```cpp #include<cstdio> #include<cstring> #include<queue> using namespace std; typedef long long ll; const int N = 500009; const ll INF = 0x3f3f3f3f3f3f3f3f; int n, m, s; struct Edge{ int to, nxt; ll w; }e[N]; int head[10009], tot; bool vis[10009]; ll dis[10009]; void add(int x, int y, ll w){ e[++tot].to = y; e[tot].w = w; e[tot].nxt = head[x]; head[x] = tot; } void spfa(int st){ queue<int> q; memset(vis, 0, sizeof(vis)); memset(dis, 0x3f, sizeof(dis)); q.push(st); dis[st] = 0; while(!q.empty()){ int x = q.front(); q.pop(); vis[x] = 0; for(int i = head[x]; i; i = e[i].nxt){ int y = e[i].to; ll w = e[i].w; if(dis[y] > dis[x] + w){ dis[y] = dis[x] + w; if(vis[y]) continue; q.push(y); vis[y] = 1; } } } } int main(){ scanf("%d%d%d", &n, &m, &s); for(int i = 1; i <= m; i++){ int x, y; ll w; scanf("%d%d%lld", &x, &y, &w); add(x, y, w); } spfa(s); for(int i = 1; i <= n; i++){ printf("%lld ", dis[i] >= INF ? 2147483647 : dis[i]); } return 0; } ``` #### 例题 - http://ybt.ssoier.cn:8088/problem_show.php?pid=1342 - http://ybt.ssoier.cn:8088/problem_show.php?pid=1343 - http://ybt.ssoier.cn:8088/problem_show.php?pid=1345 - http://ybt.ssoier.cn:8088/problem_show.php?pid=1381 - https://www.luogu.com.cn/problem/P1462（二分+Dijkstra，经典！） ### 二、并查集 #### 概念 - 一个可以查询和合并的集合 - 查询：查询两个元素是否在同一个集合中 - 合并：合并两个集合 #### 算法 - 递归实现查询 - 查询到两个集合跟节点后，让其中一个集合跟节点成为另一个根节点的儿子 #### 优化 - 查询时可能会找一个很长的链，严重降低并查集效率。 - 路径压缩 #### 实现 ```cpp #include<bits/stdc++.h> using namespace std; int n,m; int fa[10005]; int find(int x) { if(fa[x]==x) return x; return fa[x]=find(fa[x]); } int main(){ cin>>n>>m; for(int i = 0; i <= n; i++) fa[i] = i; for(int i=1;i<=m;i++) { int t,a,b,q,p; cin>>t; if(t==1) { cin>>a>>b; q=find(a),p=find(b); fa[q]=p; } if(t==2) { cin>>a>>b; q=find(a); p=find(b); if(p==q) cout<<"Y"<<endl; else cout<<"N"<<endl; } } } ``` ##### 例题 - http://ybt.ssoier.cn:8088/problem_show.php?pid=1346 - http://ybt.ssoier.cn:8088/problem_show.php?pid=1347 #### 作业 - http://ybt.ssoier.cn:8088/problem_show.php?pid=1376 - [最优乘车](http://ybt.ssoier.cn:8088/problem_show.php?pid=1377) - [最短路径](http://ybt.ssoier.cn:8088/problem_show.php?pid=1378) - [热浪](http://ybt.ssoier.cn:8088/problem_show.php?pid=1379) - [Floyd](http://ybt.ssoier.cn:8088/problem_show.php?pid=1421) - [Dijkastra(II)](http://ybt.ssoier.cn:8088/problem_show.php?pid=1420) - [搭配购买](http://ybt.ssoier.cn:8088/problem_show.php?pid=1387) - [家谱](http://ybt.ssoier.cn:8088/problem_show.php?pid=1388) - [食物链](http://ybt.ssoier.cn:8088/problem_show.php?pid=1390) - [亲戚](http://ybt.ssoier.cn:8088/problem_show.php?pid=1389) - [分糖果](http://ybt.ssoier.cn:8088/problem_show.php?pid=1380) - [【入门】有负权边的最短路](https://oj.czos.cn/p/2051) - [【基础】回家 Bessie Come Home](https://oj.czos.cn/p/2091) - [【基础】最短距离和路径问题](https://oj.czos.cn/p/2047) --- ## 第七节 图论综合应用 ### 最小生成树 #### 概念 - 生成树 - 最小生成树 #### 算法 - 输入所有边 - 按照权值排序 - 创建一个并查集 - 边权从小到大，遇到某条边所连接的两个点不在同一个集合就合并，把这条边贡献加入答案 #### 实现 ```cpp #include<cstdio> #include<algorithm> using namespace std; typedef long long ll; const int N = 200009; int n, m; struct node{ int x, y; ll w; bool operator < (const node &a){ return w < a.w; } }ed[N]; int fa[N]; int find(int x){ return x == fa[x] ? x : fa[x] = find(fa[x]); } int main(){ scanf("%d%d", &n, &m); for(int i = 1; i <= m; i++){ scanf("%d%d%lld", &ed[i].x, &ed[i].y, &ed[i].w); } sort(ed + 1, ed + m + 1); for(int i = 1; i <= n; i++) fa[i] = i; ll ans = 0; for(int i = 1; i <= m; i++){ int x = ed[i].x, y = ed[i].y; ll w = ed[i].w; int xx = find(x), yy = find(y); if(xx == yy) continue; fa[xx] = yy; ans += w; } printf("%lld\n", ans); return 0; } ``` #### 例题 - http://ybt.ssoier.cn:8088/problem_show.php?pid=1348 - http://ybt.ssoier.cn:8088/problem_show.php?pid=1350 - http://ybt.ssoier.cn:8088/problem_show.php?pid=1351 ### 课堂练习 - http://ybt.ssoier.cn:8088/problem_show.php?pid=1393 - http://ybt.ssoier.cn:8088/problem_show.php?pid=1392 - http://ybt.ssoier.cn:8088/problem_show.php?pid=1499（最短路计数） - http://ybt.ssoier.cn:8088/problem_show.php?pid=1492（最小生成树计数） - http://ybt.ssoier.cn:8088/problem_show.php?pid=1493（次小生成树） - http://ybt.ssoier.cn:8088/problem_show.php?pid=1394 - http://ybt.ssoier.cn:8088/problem_show.php?pid=1419 - https://oj.czos.cn/p/1932 ### 作业 - https://oj.czos.cn/p/1930 - https://oj.czos.cn/p/1923 - https://oj.czos.cn/p/1922 - https://oj.czos.cn/p/1929 - https://oj.czos.cn/p/1927 - https://oj.czos.cn/p/2050 - http://ybt.ssoier.cn:8088/problem_show.php?pid=1488 - http://ybt.ssoier.cn:8088/problem_show.php?pid=1487 - http://ybt.ssoier.cn:8088/problem_show.php?pid=1489 - http://ybt.ssoier.cn:8088/problem_show.php?pid=1490 - http://ybt.ssoier.cn:8088/problem_show.php?pid=1491 - http://ybt.ssoier.cn:8088/problem_show.php?pid=1501 - http://ybt.ssoier.cn:8088/problem_show.php?pid=1503 - http://ybt.ssoier.cn:8088/problem_show.php?pid=1500 ## 第八节 线性DP ### 动态规划简介 参考下列： - 动态规划是一种通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。 由于动态规划并不是某种具体的算法，而是一种解决特定问题的方法，因此它会出现在各式各样的数据结构中，与之相关的题目种类也更为繁杂。 在 OI 中，计数等非最优化问题的递推解法也常被不规范地称作 DP，因此本章将它们一并列出。事实上，动态规划与其它类型的递推的确有很多相似之处，学习时可以注意它们之间的异同。 ### DP基础 #### 什么时候用DP？ - 具有可分割的子问题 #### DP要求 - 最优子结构 - 无后效性 - 子问题重叠（子问题空间足够小，不会产生无穷的子问题） #### DP种类 - 线性、区间、树形。。。 #### DP优化 - 单调队列优化、斜率优化、不等式优化、数据结构优化。。。 ### 线性DP #### 概念 - 一般地， 具有线性划分阶段的DP，不局限于线性时间复杂度，「线性」概念类似于线性代数中的概念。 #### 最长公共子序列（LCS） - http://ybt.ssoier.cn:8088/problem_show.php?pid=1265 ##### 子序列 - 可以不连续 ##### DP一般思路 - 考虑状态，什么时候怎么样； - 考虑转移，通过一些对状态的运算使得旧的状态产生出新的状态。 ##### 状态转移方程 - 假设两个字符串，同时创建一个二维数组储存不同状态下的最优解，即最长公共子序列长度。 - 状态：$c[i][j]$表示$S_1$前$i$位字符与$S_2$前$j$位字符的情况下最长公共子序列长度。 - 转移：略 #### 最长不下降子序列（LIS） - http://ybt.ssoier.cn:8088/problem_show.php?pid=1259 ##### 状态转移 - 状态：$dp[i]$表示对于前i位的最长不下降子序列长度。 - 转移：令dp[i]等于：对于某一位i，循环从1到i-1每一位，对于所有小于第i位的取它们dp数组最大值再加一。 - 时间复杂度$O(n^2)$ #### 其他例题 - http://ybt.ssoier.cn:8088/problem_show.php?pid=1258 - http://ybt.ssoier.cn:8088/problem_show.php?pid=1260 - http://ybt.ssoier.cn:8088/problem_show.php?pid=1263 ### 作业 - http://ybt.ssoier.cn:8088/problem_show.php?pid=1264 - http://ybt.ssoier.cn:8088/problem_show.php?pid=1266 - http://ybt.ssoier.cn:8088/problem_show.php?pid=1282 - http://ybt.ssoier.cn:8088/problem_show.php?pid=1285 - https://oj.czos.cn/p/1550 - https://www.luogu.com.cn/problem/P1280 --- ## 背包问题1 ### 引入 - http://ybt.ssoier.cn:8088/problem_show.php?pid=1267 - 最一般的想法：贪心 - 分析为什么不对 - 背包 ### 概念 - 一个有容量的背包和一些给定价值和体积的物品，想往背包里装这些物品使得总价值尽量大。 ### 分类 - 01、完全、多重 ### 01背包 - 每个物品有且仅有一个 #### 算法 - 状态：$f[i][j]$表示什么 - 转移方程 - 滚动数组优化一维空间 #### 注意：优化后循环方向 ### 完全背包 - http://ybt.ssoier.cn:8088/problem_show.php?pid=1268 - 每个物品都有无穷个 #### 算法 - 状态同01 - 转移同01 - 滚动数组优化后，为什么只需要把循环方向反过来？ ### 作业 - http://ybt.ssoier.cn:8088/problem_show.php?pid=1269 - http://ybt.ssoier.cn:8088/problem_show.php?pid=1270 - http://ybt.ssoier.cn:8088/problem_show.php?pid=1291 - http://ybt.ssoier.cn:8088/problem_show.php?pid=1292 --- ## 背包问题2 ### 多重背包 - 每个物品有给定个。 #### 算法 ##### 朴素 - https://oj.czos.cn/p/1888 - 把每个物品分开看做不同物品，转化为01背包 - 效率太低 ##### 二进制拆分 - https://oj.czos.cn/p/1889 - 把每个物品按照2的幂次拆分 - 复杂度$O(nlog_2n)$ ##### 单调队列优化（后面优化再讲） ### 混合背包 - https://oj.czos.cn/p/1905 #### 算法 - 直接不同情况用不同方法完成即可 ### 作业 - https://oj.czos.cn/p/2076 - https://oj.czos.cn/p/1282 - http://ybt.ssoier.cn:8088/problem_show.php?pid=1295 - https://oj.czos.cn/p/1892 --- ## 区间DP ### 概念 区间 DP 的特点： - 合并：即将两个或多个部分进行整合，当然也可以反过来； - 特征：能将问题分解为能两两合并的形式； - 求解：对整个问题设最优值，枚举合并点，将问题分解为左右两个部分，最后合并两个部分的最优值得到原问题的最优值。 ### 算法 - 一般在一个序列上DP，通常具有区间可分性 - 以区间长度作为DP的「阶段」 - 一个状态由比当前这个区间更小的区间转移过来 - 重点是如何在区间之间转移 - 一般更喜欢采用递归的方式撰写（记忆化搜索） ### 例题 #### 石子合并 - http://ybt.ssoier.cn:8088/problem_show.php?pid=1274 - 通常区间DP的状态就是$f[l][r]$表示区间$[l,r]$ - 转移 - 如何处理环？ - 破环成链翻倍法：随便选一个地方打破环（一般就选输入的第一个），再在后面复制一遍，就可以枚举到环上所有情况（注意限制dp时区间长度小于n不是2n） ### 作业 - https://www.luogu.com.cn/problem/P4170 - http://ybt.ssoier.cn:8088/problem_show.php?pid=1570 - http://ybt.ssoier.cn:8088/problem_show.php?pid=1572 - http://ybt.ssoier.cn:8088/problem_show.php?pid=1573 - http://ybt.ssoier.cn:8088/problem_show.php?pid=1574 --- ## 树形DP ### 概念 - 因为一般对于树形的结构都采取递归处理，因此树形DP也通常使用递归的记忆化搜索完成。 - 记忆化搜索：在搜索基础上加一些记录的东西（一般就是记录题目要问的答案）在之前已经计算过某个答案时，不会再次计算，直接使用之前保存的结果。 - 题目不一定会给你一棵树，较难的题一般都会让你自己构造一棵树 ### 例题 #### 「没有上司的舞会」（经典题目） - http://ybt.ssoier.cn:8088/problem_show.php?pid=1582 - 状态：$f[x][0/1]$表示以x为根的子树快乐指数的最大值，0表示x不参加的情况，1表示x参加的情况 - 转移：x节点不参加时，x的子树最大值为所有x的儿子参加或者不参加的最大值之和。 x参加时，最大值为所有x的儿子都不参加舞会的指数之和加上x贡献的快乐指数 #### 「选课」（经典） - http://ybt.ssoier.cn:8088/problem_show.php?pid=1576 #### 「二叉苹果树」 - http://ybt.ssoier.cn:8088/problem_show.php?pid=1575 ### 作业 - http://ybt.ssoier.cn:8088/problem_show.php?pid=1577 - http://ybt.ssoier.cn:8088/problem_show.php?pid=1578 - http://ybt.ssoier.cn:8088/problem_show.php?pid=1580 - http://ybt.ssoier.cn:8088/problem_show.php?pid=1579 - https://www.luogu.com.cn/problem/P2279（经典） --- ## DP综合1 ### 例题 - http://ybt.ssoier.cn:8088/problem_show.php?pid=1261 - http://ybt.ssoier.cn:8088/problem_show.php?pid=1271 - https://oj.czos.cn/p/1902 - http://ybt.ssoier.cn:8088/problem_show.php?pid=1571 ### 作业 - http://ybt.ssoier.cn:8088/problem_show.php?pid=1262 - http://ybt.ssoier.cn:8088/problem_show.php?pid=1290 - http://ybt.ssoier.cn:8088/problem_show.php?pid=1296 - https://oj.czos.cn/p/1885 --- ## DP综合2 ### 例题 - https://www.luogu.com.cn/problem/P1220 - http://ybt.ssoier.cn:8088/problem_show.php?pid=1583 - http://ybt.ssoier.cn:8088/problem_show.php?pid=1293 - http://ybt.ssoier.cn:8088/problem_show.php?pid=1283 - http://ybt.ssoier.cn:8088/problem_show.php?pid=1289 ### 作业 - http://ybt.ssoier.cn:8088/problem_show.php?pid=1584 - http://ybt.ssoier.cn:8088/problem_show.php?pid=1294 - http://ybt.ssoier.cn:8088/problem_show.php?pid=1284 - http://ybt.ssoier.cn:8088/problem_show.php?pid=1287 - https://oj.czos.cn/p/1801 - http://ybt.ssoier.cn:8088/problem_show.php?pid=1281 --- ## ST表 ### RMQ问题 - 区间最值问题 - 给定一个长度为n的序列，m组询问，每次询问区间l到r的最大、最小值。 ### ST表 #### 算法 - 最一般的想法对于每一次询问，枚举找出最大、最小值，这样一次询问时间复杂度为$O(n)$，一共m次询问，总时间复杂度为$O(nm)$ - 如果$n,m\le 10^5$，如何优化？ - ST表使用倍增思想，$f[i][j]$表示从i开始长度为$2^j$的序列的最大值、最小值。 - 根据倍增，长度为$2^j$的序列可以分成两个长度为$2^{j-1}$的序列，因此有递推公式：$f[i][j]=max(f[i][j-1],f[i+2^{j-1}][j-1])$ - 如果要查询区间$[l,r]$的最大、最小值,查询两个可能相交的区间即可(重叠不影响求最值) - http://ybt.ssoier.cn:8088/problem_show.php?pid=1541 #### 实现 ```cpp #include<cstdio> #include<algorithm> #include<cmath> using namespace std; int n, m; int a[100009], st[100009][29]; int main(){ scanf("%d%d", &n, &m); for(int i = 1; i <= n; i++){ scanf("%d", &a[i]); st[i][0] = a[i]; } for(int i = 1; i <= 23; i++){ for(int j = 1; j + (1 << i) - 1 <= n; j++){ st[j][i] = max(st[j][i-1], st[j+(1<<(i-1))][i-1]); } } for(int i = 1; i <= m; i++){ int l, r; scanf("%d%d", &l, &r); int p = log(r - l + 1) / log(2); int ans = max(st[l][p], st[r-(1<<p)+1][p]); printf("%d\n", ans); } return 0; } ``` #### 例二 - http://ybt.ssoier.cn:8088/problem_show.php?pid=1546 ### 作业 - http://ybt.ssoier.cn:8088/problem_show.php?pid=1542 - http://ybt.ssoier.cn:8088/problem_show.php?pid=1543 - http://ybt.ssoier.cn:8088/problem_show.php?pid=1544 - http://ybt.ssoier.cn:8088/problem_show.php?pid=1545 --- ## 树状数组 ### 引入 - 求带修改操作的区间和 - 朴素方法$O(nm)$ - 考虑优化 - 树状数组 ### 算法 - http://ybt.ssoier.cn:8088/problem_show.php?pid=1535 - lowbit(x)=x&-x - 为什么用lowbit,树状数组结构. #### 单点修改 ```cpp void add(int x, int k) { while (x <= n) { c[x] = c[x] + k; x = x + lowbit(x); } } ``` #### 区间查询 ```cpp int getsum(int x) { // a[1]..a[x]的和 int ans = 0; while (x >= 1) { ans = ans + c[x]; x = x - lowbit(x); } return ans; } ``` - 区间和等于getsum(r)-getsum(l-1) - 其他例题:http://ybt.ssoier.cn:8088/problem_show.php?pid=1537 ### 作业 - http://ybt.ssoier.cn:8088/problem_show.php?pid=1540 - http://ybt.ssoier.cn:8088/problem_show.php?pid=1539 - http://ybt.ssoier.cn:8088/problem_show.php?pid=1536 - http://ybt.ssoier.cn:8088/problem_show.php?pid=1538 - https://oj.czos.cn/p/2388 --- ## 线段树 ### 概念 - 顾名思义,线段树就是以线段为节点的二叉树. - 线段树能做到的,树状数组不一定能做到,但是树状数组能做的,线段树一定能做. - 单点修改,单点查询,区间修改,区间查询. - 维护区间和,区间积,区间异或和等等. ### 原理 - 对于单点修改,区间查询的线段树http://ybt.ssoier.cn:8088/problem_show.php?pid=1547 - 修改时,从根节点开始不断向包含要修改的节点的区间递归,增加贡献. - 查询时,如果要查询的区间包含当前区间,直接加到答案里,否则继续递归. ```cpp void build(int k,int l,int r) //k表示当前结点的编号，l,r为当前结点所代表的区间 { if(l==r) //当前结点为叶子结点 { mi[k]=v; //对应区间的最小值为原序列中的对应值 return; } int mid=(l+r)/2; build(k*2,l,mid); //构造左子树 build(k*2+1,mid+1,r); //构造右子树 mi[k]=min(mi[k*2],mi[k*2+1]); //自下向上更新 } void change(int k,int l,int r,int x,int v) //x为原序列的位置，v为要改成的值 { if(r<x||l>x) return; //当前区间与原序列的位置完全无交集 if(l==r&&l==x) //当前结点为对应的叶子结点 { mi[k]=v; //修改叶子结点 return; } int mid=(l+r)/2; change(k*2,l,mid,x,v); //修改左子区间 change(k*2+1,mid+1,r,x,v); //修改右子区间 mi[k]=min(mi[k*2],mi[k*2+1]); //更新相关的值 } int query(int k,int l,int r,int x,int y) { if(y<l||x>r) return 0; if(l>=x&&r<=y) return sum[k]; int mid=l+r>>1; int res; res=query(k<<1,l,mid,x,y); res+=query(k<<1|1,mid+1,r,x,y); return res; } ``` - 对于区间修改 - 定义一个lasy_tag(懒标记) - pushdown操作 - pushup操作 ```cpp #include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 100009; struct SegmentTree { ll sum, addTag; }tree[N << 2]; int v[N]; inline int ls(int k) { return k << 1; } inline int rs(int k) { return k << 1 | 1; } void pushUp(int k) { tree[k].sum = tree[ls(k)].sum + tree[rs(k)].sum; } void build(int k, int l, int r) { if(l == r) { tree[k].sum = v[l]; return; } int mid = (l + r) >> 1; build(ls(k), l, mid); build(rs(k), mid + 1, r); pushUp(k); } void pushDown(int k, int l, int r) { if(tree[k].addTag == 0) return; int mid = (l + r) >> 1; tree[ls(k)].addTag += tree[k].addTag; tree[rs(k)].addTag += tree[k].addTag; tree[ls(k)].sum += tree[k].addTag * (mid - l + 1); tree[rs(k)].sum += tree[k].addTag * (r - mid); tree[k].addTag = 0; } void add(int k, int l, int r, int lx, int rx, ll val) { if(lx <= l && rx >= r) { tree[k].sum += val * (r - l + 1); tree[k].addTag += val; return; } pushDown(k, l, r); int mid = (l + r) >> 1; if(lx <= mid) add(ls(k), l, mid, lx, rx, val); if(rx > mid) add(rs(k), mid + 1, r, lx, rx, val); pushUp(k); } ll query(int k, int l, int r, int lx, int rx) { if(lx <= l && rx >= r) { return tree[k].sum; } pushDown(k, l, r); int mid = (l + r) >> 1; ll res = 0; if(lx <= mid) res = query(ls(k), l, mid, lx, rx); if(rx > mid) res += query(rs(k), mid + 1, r, lx, rx); return res; } int main() { int n, m; scanf("%d %d", &n, &m); for(int i = 1; i <= n; i++) { scanf("%d", &v[i]); } build(1, 1, n); for(int i = 1; i <= m; i++) { int op; scanf("%d", &op); if(op == 1) { int x, y; ll k; scanf("%d%d%lld", &x, &y, &k); add(1, 1, n, x, y, k); } if(op == 2) { int x, y; scanf("%d%d", &x, &y); ll ans = query(1, 1, n, x, y); printf("%lld\n", ans); } } return 0; } ``` - 它还可以维护区间最值,等等. ### 例题 - http://ybt.ssoier.cn:8088/problem_show.php?pid=1550 - http://ybt.ssoier.cn:8088/problem_show.php?pid=1551 ### 作业 - http://ybt.ssoier.cn:8088/problem_show.php?pid=1549 - http://ybt.ssoier.cn:8088/problem_show.php?pid=1992 - http://ybt.ssoier.cn:8088/problem_show.php?pid=1993 - http://ybt.ssoier.cn:8088/problem_show.php?pid=1994 --- ## Hash算法 ### 概念 - Hash 的核心思想在于，将输入映射到一个值域较小、可以方便比较的范围。 - 在字符串哈希中，值域需要小到能够快速比较。 同时，为了降低哈希冲突率，值域也不能太小。 - 我们定义一个把字符串映射到整数的函数$f$ ，这个$f$称为是 Hash 函数。 #### 特性 1. 在 Hash 函数值不一样的时候，两个字符串一定不一样； 2. 在 Hash 函数值一样的时候，两个字符串不一定一样（有大概率一样）。 3. 我们尽量想让在 Hash 函数值一样的时候，两个字符串一样 ### 实现 - 一般我们定义Hash函数为$f(s)=\sum^{l}_{i=1}s[i]\times b^{l-i}(mod M)$ - M是一个大素数,b可以任意取 ```cpp const int M = 1e9 + 7; const int B = 233; typedef long long ll; int get_hash(const string& s) { int res = 0; for (int i = 0; i < s.size(); ++i) { res = (ll)(res * B + s[i]) % M; } return res; } bool cmp(const string& s, const string& t) { return get_hash(s) == get_hash(t); } ``` ### 改进 - 碰撞概率比较大,一般采取对两个大质数取模,降低碰撞率. #### 多次询问子串Hash - 类似前缀和的方法,定义一个数组保存一个前缀Hash - 由于刚刚定义f(s)的特点,可以发现$f(s[l...r])=f(s[1...r])-f(s[1...l-1])\times b^{r-l+1}$ - 故可以O(n)预处理,O(1)查询,至于b的幂次可以预处理也可以快速幂 ### 例题 - http://ybt.ssoier.cn:8088/problem_show.php?pid=1455 - http://ybt.ssoier.cn:8088/problem_show.php?pid=1456 - http://ybt.ssoier.cn:8088/problem_show.php?pid=1459 - http://ybt.ssoier.cn:8088/problem_show.php?pid=1460 ### 作业 - http://ybt.ssoier.cn:8088/problem_show.php?pid=1461 - http://ybt.ssoier.cn:8088/problem_show.php?pid=1462 - http://ybt.ssoier.cn:8088/problem_show.php?pid=1463 - http://ybt.ssoier.cn:8088/problem_show.php?pid=1464 --- ## Trie树 ### 概念 - 字典树 - 用来存储一个字典,边用来保存字母,从根节点到某一节点的路径表示一个字符串. - 可以用来查询某个字符串是否出现过. ### 建立Trie树 ```cpp struct Trie { int nex[100000][26], cnt; bool exist[100000]; // 该结点结尾的字符串是否存在 void insert(char *s, int l) { // 插入字符串 int p = 0; for (int i = 0; i < l; i++) { int c = s[i] - 'a'; if (!nex[p][c]) nex[p][c] = ++cnt; // 如果没有，就添加结点 p = nex[p][c]; } exist[p] = 1; } bool find(char *s, int l) { // 查找字符串 int p = 0; for (int i = 0; i < l; i++) { int c = s[i] - 'a'; if (!nex[p][c]) return 0; p = nex[p][c]; } return exist[p]; } }; ``` ### 例题 - http://ybt.ssoier.cn:8088/problem_show.php?pid=1471 - http://ybt.ssoier.cn:8088/problem_show.php?pid=1472 - http://ybt.ssoier.cn:8088/problem_show.php?pid=1473 ### 作业 - http://ybt.ssoier.cn:8088/problem_show.php?pid=1477 - http://ybt.ssoier.cn:8088/problem_show.php?pid=1478 --- ## KMP算法 ### 前缀函数 #### 定义 #### 计算前缀函数 - 朴素方法(循环) - 时间复杂度为$O(N^3)$ ##### 优化 1. 发现相邻的前缀函数值至多增加1 2. 可以优化为$O(N^2)$ ##### 优化2 - next数组 #### 实现 ```cpp int main() { string s; cin >> s; int n = (int)s.length(); vector<int> pi(n); for (int i = 1; i < n; i++) { int j = pi[i - 1]; while (j > 0 && s[i] != s[j]) j = pi[j - 1]; if (s[i] == s[j]) j++; pi[i] = j; } } ``` ### KMP算法 - 给定一个长度为m的文本和一个长度为n的字符串，我们尝试找到字符串在文本中的所有出现. - 构造一个字符串为字符串和文本相连,中间用一个其他符号(不出现在文本和字符串中)隔开. - 计算该新字符串前缀函数 - 这个新字符串的前缀函数中,除去前n+1个以外,其余前缀函数值表示其与新字符串前缀重合的数量,由于存在分隔符,函数值不可能超过n,因此统计函数值中有几个n即为文本中有几个字符串. - 时间复杂度$O(n+m)$ #### 例题 - http://ybt.ssoier.cn:8088/problem_show.php?pid=1465 ### 作业 - http://ybt.ssoier.cn:8088/problem_show.php?pid=1467 - http://ybt.ssoier.cn:8088/problem_show.php?pid=1468 - http://ybt.ssoier.cn:8088/problem_show.php?pid=1470 --- ## 质数 ### 定义 - 约数只有1和它本身的数. ### 质数判断 - 朴素算法:判断2到n-1是否存在其约数. - 时间复杂度$O(n)$ - 优化:判断2到$\sqrt{n}$是否存在其约数 - 解释:约数一定成对出现,如果$[\sqrt{n},n-1]$存在约数,必定存在$[2,\sqrt{n}]$的对应约数. - 时间复杂度$O(\sqrt{n})$ ### 质数筛法 #### 问题 - 找出2~n所有素数 - 分别判断每个数是否为素数,时间复杂度$O(n\sqrt{n})$. - 筛法 #### 埃氏筛 - 对于每个数,它的倍数一定不是质数,因此对于每个数都将它到n所有它的倍数标记,这样每遇到一个没被标记的数都是一个质数. - 时间复杂度为$\frac{n}{2}+\frac{n}{3}+\frac{n}{5}+\frac{n}{7}+\frac{n}{11}+...$ - 即$n(\frac{1}{2}+\frac{1}{3}+\frac{1}{5}+\frac{1}{7}+\frac{1}{11}+...)$ - 根据数学定理证明$\frac{1}{2}+\frac{1}{3}+\frac{1}{5}+\frac{1}{7}+\frac{1}{11}+...=lnln(n)$ - 具体证明见下图  ##### 模板 ```cpp int Eratosthenes(int n) { int p = 0; for (int i = 0; i <= n; ++i) is_prime[i] = 1; is_prime[0] = is_prime[1] = 0; for (int i = 2; i <= n; ++i) { if (is_prime[i]) { prime[p++] = i; // prime[p]是i,后置自增运算代表当前素数数量 if ((long long)i * i <= n) for (int j = i * i; j <= n; j += i) // 因为从 2 到 i - 1 的倍数我们之前筛过了，这里直接从 i // 的倍数开始，提高了运行速度 is_prime[j] = 0; // 是i的倍数的均不是素数 } } return p; } ``` ### 例题 - http://ybt.ssoier.cn:8088/problem_show.php?pid=1619 - http://ybt.ssoier.cn:8088/problem_show.php?pid=1620 - https://oj.czos.cn/p/2071 ### 作业 - https://oj.czos.cn/p/2007 - https://oj.czos.cn/p/1942 - http://ybt.ssoier.cn:8088/problem_show.php?pid=1621 - http://ybt.ssoier.cn:8088/problem_show.php?pid=1622 - http://ybt.ssoier.cn:8088/problem_show.php?pid=1624 --- ## 快速幂 ### 问题引入 - 求a的b次方,结果对1000000007取模 - 朴素解法,循环b次,每次乘a,取模 - 时间复杂度$O(b)$ - 经常会计算$b\leq 10^{18}$ - 超时 ### 算法 - 已知任何一个数都有二进制,因此可以将b二进制拆分 - 例如$b=2^{p_1}+2^{p_2}+2^{p_3}+2^{p_4}+...+2^{p_n}$ - 那么,$a^b=a^{2^{p_1}}a^{2^{p_2}}...a^{2^{p_n}}$ - 易证明$n\le log_2b$ - 因此可以优化到时间复杂度$O(log_2b)$ ### 实现 ```cpp #include<bits/stdc++.h> using namespace std; typedef long long ll; const ll mod = 1e9 + 7; ll power(ll a, ll b) { ll res = 1; while(b) { if(b & 1) res = res * a % mod; a = a * a % mod; b >>= 1; } return res; } int main() { int a, b; cin >> a >> b; cout << power(a, b); return 0; } ``` ### 例题 http://ybt.ssoier.cn:8088/problem_show.php?pid=1615 ### 作业 http://ybt.ssoier.cn:8088/problem_show.php?pid=1616 http://ybt.ssoier.cn:8088/problem_show.php?pid=1617 http://ybt.ssoier.cn:8088/problem_show.php?pid=1618 --- ## 约数 ### 整除 - 数论是一类解决整数之间的问题的理论,因此整除是一个重要的理论 #### 定义 - 对于两整数a,b如果存在整数c使得$a=bc$则称a被b整除,即b整除a,记作$b|a$. - 此时,b是a的约数,a是b的倍数 #### 性质 - 3条 ### 约数 #### 定义 #### 定理 ##### 算数基本定理(唯一分解定理) - 对于任意正整数n可被唯一分解为$n=p_1^{a_1}p_2^{a_2}p_3^{a_3}...p_m^{a_m}$. - 其中$p_i$是质数 - n的约数个数可表示为$(a_1+1)(a_2+1)...(a_m+1)$ #### 求一个数的所有约数 - 试除法 - 从1试到$\sqrt{n}$ #### 求1~n所有数的约数 - 将每个数的倍数添加到对应数的约数 - 时间开销$n(1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+...+\frac{1}{n})=nlogn$ - 上述级数求和无需掌握,但结论要记 ### 最大公约数 #### 公约数 - 两个数公共的约数 #### 公倍数 - 两个数公共的倍数 #### 定理 - 如果a和b的最大公约数为c,那么a和b的最小公倍数为a*b/c - 最大公约数缩写gcd,最小公倍数缩写lcm #### 欧几里得辗转相除法求最大公约数 - a和b的最大公约数等于a和a%b的最大公约数 ##### 实现 ```cpp int gcd(int a, int b) { if(b == 0) return a; return gcd(b, a % b); } ``` ### 哥德巴赫猜想 - 任一大于5的整数都可写成三个质数之和。 - n>5时,当n为偶数，n=2+(n-2)，n-2也是偶数，可以分解为两个质数的和；当n为奇数，n=3+(n-3)，n-3也是偶数，可以分解为两个质数的和. - 欧拉提出的另外一个表述,任一大于2的偶数都可写成两个质数之和. - 以上只是猜想,无证明,但可以作为结论直接用!!! ### 例题 - http://ybt.ssoier.cn:8088/problem_show.php?pid=1625 - http://ybt.ssoier.cn:8088/problem_show.php?pid=1626 - http://ybt.ssoier.cn:8088/problem_show.php?pid=1627 ### 作业 - http://ybt.ssoier.cn:8088/problem_show.php?pid=1628 - http://ybt.ssoier.cn:8088/problem_show.php?pid=1629 - http://ybt.ssoier.cn:8088/problem_show.php?pid=1630 - https://oj.czos.cn/p/2194 --- ## 矩阵乘法 ### 矩阵 - 一个n\*m的矩阵可看作一个n\*m的二维数组,矩阵的加法和减法，就是把两个矩阵对应位置上的数加减. - 矩阵乘法具体定义过繁琐可以百度 - 对于线性的递推关系式可以使用矩阵表示。 - 斐波那契数列,递推式为$a_n=a_{n-1}+a_{n-2}$ - 矩阵表示为: 将$F_n$表示矩阵$[a_n, a_{n-1}]$ 那么递推式可以为 $$ F_n=F_{n-1}\times A\\ 其中A=\begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix} $$ 那么求斐波那契额数列可以用这个公式直接算,其中A的幂次可以使用快速幂,因此时间复杂度可以优化到$O(logn)$ #### 实现 ```cpp #include<bits/stdc++.h> using namespace std; typedef long long ll; ll mod; struct node{ ll array[3][3]; void init(ll x, ll y, bool f){ if(f){ array[1][1] = y, array[1][2] = x; } else{ array[1][1] = x, array[2][1] = y; array[1][2] = 1, array[2][2] = 0; } } void init0(){ memset(array, 0, sizeof(array)); } }; struct Solution{ ll p, q, n, m, a1, a2; node ans, A; node mul(node x, node y){ node c; c.init0(); for(int i = 1; i <= 2; i++){ for(int j = 1; j <= 2; j++){ for(int k = 1; k <= 2; k++){ c.array[i][j] += (x.array[i][k] % mod * y.array[k][j] % mod) % mod; c.array[i][j] %= mod; } } } return c; } void power(ll q){ while(q){ if(q & 1) ans = mul(ans, A); A = mul(A, A); q >>= 1; } } void Solve(){ scanf("%lld", &n); p = 1, q = 1, a1 = 1, a2 = 1; mod = 1e9 + 7; ans.init(a1, a2, 1); A.init(p, q, 0); if(n == 1){ printf("%lld\n", a1); return; } if(n == 2){ printf("%lld\n", a2); return; } power(n - 2); printf("%lld\n", ans.array[1][1]); } }; int main(){ Solution().Solve(); return 0; } ``` ### 例题 - http://ybt.ssoier.cn:8088/problem_show.php?pid=1641 - http://ybt.ssoier.cn:8088/problem_show.php?pid=1642 - http://ybt.ssoier.cn:8088/problem_show.php?pid=1643 ### 作业 - http://ybt.ssoier.cn:8088/problem_show.php?pid=1644 - http://ybt.ssoier.cn:8088/problem_show.php?pid=1645 - http://ybt.ssoier.cn:8088/problem_show.php?pid=1646 - http://ybt.ssoier.cn:8088/problem_show.php?pid=1647 --- ## 同余 ### 同余定义 - 如果整数a,b除以正整数m的余数相等,则称a,b模m同余,记作$a\equiv b\pmod m$ ### 费马小定理 - 若p是质数,则对于任意质数a,有$a^p \equiv a\pmod p$ - 证明需要引入同余类和剩余系,在此不赘述 ### 欧拉定理 - 若正整数a,n互质,则$a^{\phi(n)}\equiv 1\pmod n$,其中$\phi(n)$为欧拉函数 - 证明同上 #### 推论 - 若正整数a,n互质,则对于任意正整数b,都有$a^b\equiv a^{b\mod \phi(n)}\pmod n$ - 换句话说,对于很多问题输出答案对一个大质数p的模数,对于a+b,a\*b可以先分别对a,b取模再相加/乘.对于乘方,可以先让底数对p取模,指数对$\phi(p)$取模再计算乘方. ### 扩展欧几里得算法 - http://ybt.ssoier.cn:8088/problem_show.php?pid=1631 #### 裴蜀定理(贝祖定理) - 对于任意整数a,b,存在一对整数x,y,满足$ax+by=gcd(a,b)$ ##### 证明 - 由欧几里得的递归方法,在辗转相除法最后一步,b=0时,显然存在$x=1,y=0$使得$ax+by=a$ - 如果b>0,那么由$gcd(a,b)=gcd(b,a\mod b)$. 假设存在一对整数x,y,满足$bx+(a\mod b)y=gcd(b,a\mod b)$,因为$bx+(a\mod b)y=bx+(a-b\lfloor a/b\rfloor)y=ay+b(x-\lfloor a/b\rfloor)$,所以令$x^{'}=y,y^{'}=x-\lfloor a/b\rfloor y$,就得到了$ax^{'}+by^{'}=gcd(a, b)$。 - 之和利用数学归纳法即可证明裴蜀定理 ##### 由裴蜀定理证明得到扩展欧几里得算法,求出x,y ```cpp int exgcd(int a, int b, int &x, int &y) { if(b == 0) { x = 1, y = 0; return a; } int gcdab = exgcd(b, a % b, x, y); int z = x; x = y; y = z - y * (a / b); return d; } ``` 这样求出来其中一组特解 ### 乘法逆元 - http://ybt.ssoier.cn:8088/problem_show.php?pid=1633 #### 定义 - 若b,m互质,并且$b|a$,则存在一个整数x使得$a/b\equiv a*x\pmod m$,称x为b的模m乘法逆元,记为$b^{-1}\pmod m$ #### m为质数 - 如果m是质数,并且b<m,根据费马小定理,$b^{m-1}\equiv1\pmod m$,即$b*b^{p-2}\equiv 1\pmod m$ - 因此当模数为质数时,$b^{m-2}$即为b的乘法逆元(快速幂计算即可). #### m不是质数,但是m与b互质 - 那么只需求解线性同余方程$b*x\equiv 1\pmod m$ - 使用扩展欧几里得计算即可 - 到此,在模p意义下的加,减,乘,除,乘方运算均有适当的处理方法 ### 线性同余方程 - http://ybt.ssoier.cn:8088/problem_show.php?pid=1632 #### 概念 - 形如$ax\equiv c\pmod m$的方程被称为 线性同余方程。 #### 计算 ##### 定理1 - 原方程等价与$ax+by=c$,根据裴蜀定理,其有整数解的充要条件是$gcd(a, b)|c$ - 因此,我们只需先使用扩展欧几里得计算出$ax+by=gcd(a, b)$的解,再将两边同时乘$\frac{c}{gcd(a, b)}$即可 ##### 定理2 - 若gcd(a,b)=1,对于一组特解$x_0,y_0$存在通解$x=x_0+bt,y=y_0-at,t\in Z$ - 根据此定理可以求出方程所有解,一般最小整数解为$x=(x\mod t + t) \mod t$其中$t=\frac{b}{gcd(a, b)}$ ```cpp int exgcd(int a, int b, int &x, int &y) { if(b == 0) { x = 1, y = 0; return a; } int gcdab = exgcd(b, a % b, x, y); int z = x; x = y; y = z - y * (a / b); return d; } bool liEu(int a, int b, int c, int& x, int& y) { int d = exgcd(a, b, x, y); if (c % d != 0) return 0; int k = c / d; x *= k; y *= k; return 1; } ``` ### 作业 - http://ybt.ssoier.cn:8088/problem_show.php?pid=1637 - http://ybt.ssoier.cn:8088/problem_show.php?pid=1638 Last modification：February 8, 2022 © Reprint prohibited Like 1 如果觉得我的文章对你有用，请随意赞赏