跳转至

数学部分简介

在 OI/ACM 的各种比赛中,常常会有数学题的出现。

这些数学题以数论、排列组合、概率期望、多项式为代表,可以出现在几乎任何类别的题目中。

举几个栗子:

  1. 多项式可以优化卷积形式的背包,可以做一些字符串题。
  2. 很多 DP 类型的题都可以结合排列组合/概率期望。

以下是你可以在本部分找到的知识(部分未完成,待补充)

  1. 进制:多种进制的介绍与互相转化。
  2. 位运算:二进制下的按位运算(与、或、非等)。
  3. 高精度:当数字过大,语言变量类型不足以存储时的处理方法。
  4. 整除:质数、最大公约数、欧拉函数与欧拉定理、(类)欧几里德算法。
  5. 同余:裴蜀定理、逆元、中国剩余定理、大步小步(BSGS)算法、阶与原根。
  6. 线性代数基础:矩阵、高斯消元(矩阵/概率期望)、线性基。
  7. 复数与复平面
  8. 数论反演:主要有莫比乌斯反演。
  9. 筛法:埃氏筛、欧拉筛(线性筛)、杜教筛/洲阁筛。
  10. 多项式:快速傅里叶变换(FFT)、快速数论变换(NTT),拉格朗日插值、多项式的各种变换。
  11. 组合数学:排列组合、卡特兰数、斯特林数、康托展开、容斥原理、抽屉原理。
  12. 概率与期望
  13. 置换
  14. 线性规划
  15. 单纯形算法
  16. 博弈论算法
  17. 快速幂算法
  18. 向量
  19. 极坐标与极坐标系
  20. 其他算法

OI 中的数学以高中,大学的数学为基础,考察选手对数学知识的掌握,利用计算机的计算能力来解决问题。

NOIP 中有可能会考察的知识点

然而 NOIP 可能考察更多的知识点,这里只是利用之前的题总结出来的,考过或者考的概率比较大的知识点。

NOIP 对数学的考察还处在一个比较简单的范围。

  1. 进制相关——通常是利用进制优化一些问题
  2. 位运算——状压常用
  3. 高精度——不包括需要利用多项式的高精度
  4. 整除性质—— \gcd ,欧拉函数,费马小定理
  5. 同余相关—— exgcd ,逆元,中国剩余定理
  6. 概率期望——概率 DP,以及有可能用到高斯消元解决的概率 DP
  7. 排列组合——杨辉三角,二项式定理,卢卡斯定理,卡特兰数
  8. 数论问题——素数(质数),快速幂,找规律

常见符号

在学习数论的过程中大家会见到许多复杂的公式符号。因此在学习具体内容之前,建议大家首先理解下列常见符号的含义。一些特殊的符号会在对应的章节中讲到,而这里则有一些极为常见的符号需要大家提前掌握。

复杂度函数

  1. O 符号:当且仅当存在正实数 M 和实数 x_0 ,使得 \forall x\geq x_0,\ |f(x)|\leq M|g(x)| ,我们就可以认为, f(x)=O(g(x))
  2. \Omega 符号:当且仅当存在正实数 M 和实数 x_0 ,使得 \forall x\geq x_0,\ f(x)\geq Mg(x) ,我们就可以认为, f(x)=\Omega (g(x)) . 大 O 与大 \Omega 恰好相反,即 f(x)=O(g(x))\Leftrightarrow g(x)=\Omega(f(x))
  3. \Theta 符号:大 \Theta 符号是大 \text{O} 和大 \Omega 的结合,即 f(x)=O(g(x))\wedge f(x)=\Omega(g(x))\ \Rightarrow f(x)=\Theta(g(x))

整除/同余理论常见符号

  1. 整除符号: x\mid y ,表示 x 整除 y ,即 x y 的因数。
  2. 取模符号: x\bmod y ,表示 x 除以 y 得到的余数。
  3. 互质符号: x\perp y ,表示 x , y 互质。
  4. 最小公倍数: \gcd(x,y) ,在无混淆意义的时侯可以写作 (x,y)
  5. 最大公约数: \operatorname{lcm}(x,y) ,在无混淆意义的时侯可以写作 [x,y]

数论函数常见符号

求和符号: \sum 符号,表示满足特定条件的数的和。举几个例子:

  • \sum_{i=1}^n i 表示 1+2+\cdots+n 的和。其中 i 是一个变量,在求和符号的意义下 i 通常是 正整数或者非负整数 (除非特殊说明)。这个式子的含义可以理解为, i 1 循环到 n ,所有 i 的和。这个式子用代码的形式很容易表达。当然,学过简单的组合数学的同学都知道 \sum_{i=1}^n i=\frac{n(n+1)}{2}
  • \sum_{S\subseteq T}|S| 表示所有被 T 包含的集合的大小的和。
  • \sum_{p\le n,p\perp n}1 表示的是 n 以内有多少个与 n 互质的数,即 \varphi(n) \varphi 是欧拉函数。

求积符号: \prod 符号,表示满足特定条件的数的积。举几个例子:

  • \prod_{i=1}^ni 表示 n 的阶乘,即 n! 。在组合数学常见符号中会讲到。
  • \prod_{i=1}^na_i 表示 a_1\times a_2\times a_3\times \cdots\times a_n
  • \prod_{x|d}x 表示 d 的所有因数的乘积。

在行间公式中,求和符号与求积符号的上下条件会放到符号的上面和下面,这一点要注意。

其他常见符号

  1. 阶乘符号 ! n! 表示 1\times 2\times 3\times \cdots\times n
  2. 向下取整符号: \lfloor x\rfloor ,表示小于等于 x 的最大的整数。常用于分数,比如分数的向下取整 \left\lfloor\frac{x}{y}\right\rfloor
  3. 向上取整符号: \lceil x\rceil ,与向下取整符号相对,表示大于等于 x 的最小的整数。

另外,还请大家学好高一数学,这样学习数论的时侯会省很多功夫。


评论