【NOI 2】数学 1

## Chapter 0. 引言 数学是与 OI 紧密相关的基础学科，在 OI 中有着极为广泛的应用。 在学习数学专题前，建议掌握高中数学的大部分内容，并能够在实际中进行应用。 在学习数学专题时，首先要熟悉相关知识点，然后在做题的过程中不断学习如何应用数学思维与数学方法，最后总结出一套面对数学问题的处理方式。 ## Chapter 1. 组合计数 组合计数一直是 OI 中经久不衰的内容，且常常与动态规划、数据结构等内容相结合。 #### Part 1. 计数原理 - 加法原理和乘法原理是组合数学中最基础的计数原理。有大量的组合计数题目只需要通过这两个原理的反复应用即可完成。请完成以下题目：P8557，P5303，P8321，并思考在做题过程中应如何使用加法原理和乘法原理。 - 算两次原理是数学中常用的一种方法，在 OI 中的体现即为从不同的角度计算答案，如维度的变换（枚举下标/权值）、贡献的计算（直接计算/增量计算）等。选择合适的角度后，再使用加法原理和乘法原理等计数方法解决问题。 - 抽屉原理（鸽巢原理）常用于存在性证明与极端情况求解，与该原理相关的题目有：P7738，同学们可以选择性完成。 #### Part 2. 组合数 组合数是最基础的组合工具。 - 组合数的计算 - 递推：$\binom{n}{m} = \binom{n - 1}{m} + \binom{n - 1}{m - 1}$。请完成以下题目：P2822，P5239。 - 阶乘：$\binom{n}{m} = \frac{n!}{m!(n-m)!} = \frac{n^{\underline{m}}}{m!}$。请完成以下题目：P8576。 - Lucas 定理。请完成以下题目：P3773。 - 组合恒等式：吸收恒等式、行求和、列求和、范德蒙德卷积。请完成以下题目：P8594，P8367。 - 组合数的应用 - 隔板法与捆绑法。请完成以下题目：P4562。 - 与加法原理和乘法原理相结合。请完成以下题目：P2606，P8863。 - 格路计数与卡特兰数。请完成以下题目：P3266。 #### Part 3. 容斥原理 & 反演 - 容斥原理是非常重要的计数原理，能够对问题的角度进行转化，弱化/加强问题的限制，从而使问题更加简洁。请完成以下题目：P3813，P5664，P6076，P8329。 - 反演是容斥原理的代数形式，同学们可以尝试自行推导子集反演与二项式反演的公式。请完成以下题目：P4491，P6478。 #### Part 4. 多项式与生成函数基础 - 拉格朗日插值是沟通多项式的系数形式与点值形式的重要公式，近年来多次在省选与 NOI 中考察。学习该部分内容，不仅要熟记插值公式，更要形成对多项式的认知能力。请完成以下题目：P4463，P5469，P8290。 - FFT 与 NTT 虽然被划定为 10 级算法，但是单位根的良好性质同样可以应用于其它场合（如单位根反演），同时多项式乘法是许多问题中不可避免的一环。建议同学们在理解原理后背住一份模板，在平时的做题过程中可能会涉及，考场上也可以应对部分题目的暴力。 - 生成函数是用于刻画数列的组合工具，能够将很多复杂的组合问题赋以简洁的代数形式。同学们可以尝试用生成函数方法推导组合恒等式，体会代数手段的应用方式。请完成以下题目：P3746，P8558。 #### Part 5. 组合杂项 - 错排数。请完成以下题目：P4071。 - 斐波那契数列。 - Prufer 序。请完成以下题目：P2290。 - 斯特林数。请选择性完成以下题目：P4609，P6620，P8859。 - 学有余力的同学可以进一步了解贝尔数、伯努利数、分拆数、欧拉数的相关知识。 #### Part 6. 组合综合 - 请选择性完成以下题目：P8362，P8332。 ## Chapter 2. 概率期望 #### Part 1. 概率 - 古典概型：样本空间为有限集，常转化为计数问题进行计算。请完成以下题目：P3978。 - 几何概型：样本空间为无限集，常用几何方法计算，可以用于描述两个连续随机变量间的大小关系。 - 概率的运算：独立事件的概率，贝叶斯公式。 #### Part 2. 期望 - 期望的定义与性质。 - 期望的线性性：$E(X + Y) = E(X) + E(Y)$。请完成以下题目：P1654，P5472。 - min-max 容斥：$E(\max_{x \in S} \{x\}) = \sum_{T \subseteq S} (-1) ^ {|T| + 1} E(\min_{x \in T} \{x\})$。请完成以下题目：P3175。min-max 容斥可以推广到第 $k$ 大的形式，学有余力的同学可以进一步了解，并选择性完成以下题目：P4707。 - 方差计算公式：$D(X) = E(X ^ 2) - E^2(X)$。 #### Part 3. 应用 在实际问题中，概率期望往往与动态规划等类似的结构相结合，需要根据题目设计状态，计算每个状态对应的概率期望。 - 状态间满足拓扑序的问题：可以按照拓扑序直接求解。请完成以下题目：P4284，P4206。 - 状态间不满足拓扑序的问题，一般通过高斯消元求解。请完成以下题目：P3211。特别地，对于特殊的矩阵，如关系图形成线性结构、树形结构时，可以采用主元法/待定系数法进行求解。请完成以下题目：P3750，P4457，P5643。