《算法竞赛进阶指南》笔记
2021/11/15 22:12:21
本文主要是介绍《算法竞赛进阶指南》笔记,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
目录- 0x30 数学知识
- 0x33 同余
- 概念与定理
- 例题The Luckiest Number
- 扩展欧几里得算法$(exgcd)$
- 定理及概念
- 线性同余方程
- 高次同余方程
- 概念与定理
- 0x34 矩阵乘法
- 0x35 高斯消元与线性空间
- 高斯消元
- 线性空间
- 0x36 组合计数
- 基本概念
- 组合数的求法
- 二项式定理
- 多重集的排列数与组合数
- Lucas 定理
- Catalan 数列
- 0x33 同余
0x30 数学知识
0x33 同余
概念与定理
定义: 如果\(a\%m = b\%m\),则 \(a\) 与 \(b\) 模 \(m\) 同余, \(m\) 为正整数,记作 \(a\equiv b\pmod m\)
同余类: 对于 \(\forall a \subset [0, m-1]\) ,集合 \({a+km}(k\subset Z)\) 的所有模 \(m\) 同余,余数都是 \(a\)。该集合就是一个模 \(m\) 的同余类,记为 \(\bar{a}\)。
完全剩余系: 模 \(m\) 的同余类一共有 \(m\) 个,分别为 \(\bar{1},\bar{2},\dots,\overline{m-1}\) ,是一个完全剩余系。
简化剩余系: \(1~m\) 中与 \(m\) 互质的数代表的同余类共有\(\varphi(m)\) 个,它们构成 \(m\) 的简化剩余系,例如,模 \(10\) 的简化剩余系为 \({\bar{1}, \bar{3}, \bar{7}, \bar{9}}\) 。( \(\varphi(n)\) 大小为小于 \(n\) 的所有与 \(n\) 互质的正整数个数)
若 \(a, b(1 ≤ a,b ≤ m)\) 与 \(m\) 互质, 则 \(a*b\) 与 \(m\) 也互质,也能属于 \(m\) 的简化剩余系。
费马小定理: 若 \(p\) 是质数,则对于任意整数 \(a\),有 \(a^p\equiv a\pmod p\)。
欧拉定理: 若正整数 \(a,n\) 互质,则 \(a^{\varphi(n)}\equiv 1\pmod n\),其中 \(\varphi(n)\) 为欧拉函数。
(证明略)
其中,若 \(p\) 是一个质数,则 \(\varphi(p) = p - 1\)。
欧拉定理的推论: 若正整数 \(a,n\) 互质,则对于任意正整数 \(b\),有 \(a^b\equiv a^{b\mod \varphi(n)}\pmod n\)。
对答案取模 \(p\) 的应用技巧:
- 面对 \(a+b,a-b,a*b\) 这种算式,先对 \(a,b\) 分别对 \(p\) 取模。
- 面对乘法算式, 根据欧拉定理的推论,先将底数对 \(p\) 取模$、质数对 \(\varphi(p)\) 取模,再计算乘方。
- 特别地,当 \(a,n\) 不一定互质且 \(b>\varphi(n)\) 时,有 \(a^b\equiv a^{b\mod \varphi(n) + \varphi(n)}\pmod n\),即意味着,即便底数 \(a\) 与 模数 \(n\) 不互质,也能把指数的规模给缩小。 (指数循环节证明)
例题The Luckiest Number
此题由欧拉函数引出一个推理:
- 满足 \(a^x\equiv1\pmod n\) 的最小的 \(x\), \(x_0\) 是 \(\varphi(n)\) 的约数。
此题启发点:
- \(x\) 个 \(8\) 连起来的数可以写作 \(8(10^x-1)/9\),题意是求最小的 \(x\),满足 \(L\mid 8(10^x -1)\)。设 \(d=gcd(L,8)\),然后推导运用引理。
扩展欧几里得算法\((exgcd)\)
定理及概念
\(Bezout\) 定理:对于任意整数 \(a,b\) ,存在一对整数 \(x,y\), 满足 \(ax+by=gcd(a,b)\)。
乘法逆元:
线性同余方程
高次同余方程
0x34 矩阵乘法
0x35 高斯消元与线性空间
高斯消元
线性空间
0x36 组合计数
基本概念
加法原理: 完成一件事有 \(n\) 类方法,其中第 \(i\) 类方法包括 \(a_i\) 种不同的方法,且方法之间相互独立,则完成这件事共有 \(a_1+a_2+\ldots+a_n\) 种不同方法。
乘法原理: 完成一件事要 \(n\) 个步骤,其中第 \(i\) 个步骤有 \(a_i\) 种不同的方法,方法、步骤之间相互独立,则完成这件事共有 \(a_1*a_2*\cdots*a_n\) 种不同方法。
排列数: 从 \(n\) 个不同元素中依次取出 \(m\) 个元素排成一列,产生的不同排列的数量为:
\[A_n^m(也可记作P_n^m)=\frac{n!}{(n-m)!}=n*(n-1)*\cdots*(n-m+1) \]组合数: 从 \(n\) 个不同的元素中取出 \(m\) 个组成一个集合(无顺序),产生的不同集合数量为:
\[C_n^m=\frac{n!}{m!(n-m)!}=\frac{n*(n-1)*\cdots*(n-m+1)}{m*(m-1)*\cdots*2*1} \]组合数性质:
- \(C_n^m=C_n^{n-m}\)
- \(C_n^m = C_{n-1}^m + C_{n-1}^{m-1}\)
- \(C_n^0+C_n^1+C_n^2+\cdots+C_n^m=2^n\)
组合数的求法
二项式定理
多重集的排列数与组合数
Lucas 定理
Catalan 数列
这篇关于《算法竞赛进阶指南》笔记的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-11-01后台管理开发学习:新手入门指南
- 2024-11-01后台管理系统开发学习:新手入门教程
- 2024-11-01后台开发学习:从入门到实践的简单教程
- 2024-11-01后台综合解决方案学习:从入门到初级实战教程
- 2024-11-01接口模块封装学习入门教程
- 2024-11-01请求动作封装学习:新手入门教程
- 2024-11-01登录鉴权入门:新手必读指南
- 2024-11-01动态面包屑入门:轻松掌握导航设计技巧
- 2024-11-01动态权限入门:新手必读指南
- 2024-11-01动态主题处理入门:新手必读指南