跳转至

数学部分简介

数学部分简介

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

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

举几个栗子 :

  1. 多项式可以优化卷积形式的背包,可以做一些字符串题

  2. 很多 DP 类型的题都可以结合排列组合 / 概率期望。


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

  1. 进制相关
  2. 位运算 —— 二进制下的按位运算
  3. 高精度 —— 当语言变量类型不足以表达需要表达的数时的处理方法
  4. 整除性质 (数论)
  5. 同余相关 (数论)
  6. 高斯消元 (矩阵 / 概率期望)
  7. 数论反演
  8. 杜教筛 / 洲阁筛
  9. 多项式 (FFT, NTT, FWT, 拉格朗日差值)
  10. 排列组合 (Lucas, Catalan)
  11. 概率与期望
  12. 置换
  13. 线性规划
  14. 线性基

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

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

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

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

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

评论