数学部分简介
数学部分简介¶
在 OI/ACM 的各种比赛中，常常会有数学题的出现。
这些数学题以数论、排列组合、概率期望、多项式为代表，可以出现在几乎任何类别的题目中
举几个栗子：
多项式可以优化卷积形式的背包，可以做一些字符串题
很多 DP 类型的题都可以结合排列组合/概率期望。
以下是你可以在本部分找到的知识（部分未完成，待补充）¶
- 进制相关
- 位运算——二进制下的按位运算
- 高精度——当语言变量类型不足以表达需要表达的数时的处理方法
- 整除性质（数论）
- 同余相关（数论）
- 高斯消元（矩阵/概率期望）
- 数论反演
- 杜教筛/洲阁筛
- 多项式（FFT, NTT, FWT, 拉格朗日插值）
- 排列组合 (Lucas, Catalan)
- 概率与期望
- 置换
- 线性规划
- 线性基
OI 中的数学以高中，大学的数学为基础，考察选手对数学知识的掌握，利用计算机的计算能力来解决问题。
NOIP 中有可能会考察的知识点¶
然而 NOIP 可能考察更多的知识点，这里只是利用之前的题总结出来的，考过或者考的概率比较大的知识点。
NOIP 对数学的考察还处在一个比较简单的范围。
- 进制相关——通常是利用进制优化一些问题
- 位运算——状压常用
- 高精度——不包括需要利用多项式的高精度
- 整除性质—— ，欧拉函数，费马小定理
- 同余相关—— ，逆元，中国剩余定理
- 概率期望——概率 DP，以及有可能用到高斯消元解决的概率 DP
- 排列组合——杨辉三角，二项式定理，卢卡斯定理，卡特兰数
build本页面最近更新：，更新历史
edit发现错误？想一起完善？ 在 GitHub 上编辑此页！
people本页面贡献者：
copyright本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用