【学习 3】数学1

# 学习指导 ## Chapter 0. 引言 数学是与 OI 紧密相关的基础学科，在 OI 中有着极为广泛的应用。 在学习数学专题前，建议同学掌握高中数学的大部分内容，并能够在实际中进行应用。 在学习数学专题时，首先要熟悉相关知识点，然后在做题的过程中不断学习如何应用数学思维与数学方法，最后总结出一套面对数学问题的处理方式。 ## Chapter 1. 组合计数 组合计数一直是 OI 中经久不衰的内容，且常常与动态规划、数据结构等内容相结合。 #### Part 1. 计数原理 - 加法原理和乘法原理是组合数学中最基础的计数原理。有大量的组合计数题目只需要通过这两个原理的反复应用即可完成。请完成以下题目：P8557，P5303，P8321，并思考在做题过程中应如何使用加法原理和乘法原理。 - 算两次原理是数学中常用的一种方法，在 OI 中的体现即为从不同的角度计算答案，如维度的变换（枚举下标/权值）、贡献的计算（直接计算/增量计算）等。选择合适的角度后，再使用加法原理和乘法原理等计数方法解决问题。 - 抽屉原理（鸽巢原理）常用于存在性证明与极端情况求解，与该原理相关的题目有：P7738，同学们可以选择性完成。 #### Part 2. 组合数 组合数是最基础的组合工具。 - 排列数 - 排列数的计算：$n!=n\times(n-1)\times(n-2)\times\cdots\times1$，请完成以下题目：P1706 - 组合数的计算 - 递推：$\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，P1641。 - Lucas 定理。请完成以下题目：P3773，P8688。 - 吸收恒等式，这是对于组合数的一种变换方法。请完成以下题目：P8594，P8367。 - 二项式定理：二项式定理是一种用组合数把指数进行展开的公式，请完成以下题目：P4456 - 组合数的应用 - 隔板法与捆绑法。请完成以下题目：P4562。 - 与加法原理和乘法原理相结合。请完成以下题目：P2606，P8863。 - 格路计数与卡特兰数。请完成以下题目：P3266。 #### Part 3. 容斥原理 & 反演 - 容斥原理是非常重要的计数原理，能够对问题的角度进行转化，弱化/加强问题的限制，从而使问题更加简洁。请完成以下题目：P3197，P6692。 - 反演是容斥原理的代数形式，同学们可以尝试自行推导子集反演与二项式反演的公式。请完成以下题目：P1450。 #### Part 4. 多项式与生成函数基础 - 拉格朗日插值是沟通多项式的系数形式与点值形式的重要公式，近年来多次在省选与 NOI 中考察。学习该部分内容，不仅要熟记插值公式，更要形成对多项式的认知能力。请完成以下题目：P5469，P8290。 - FFT 与 NTT 虽然被划定为 10 级算法，但是单位根的良好性质同样可以应用于其它场合（如单位根反演），同时多项式乘法是许多问题中不可避免的一环。建议同学们在理解原理后背住一份模板，在平时的做题过程中可能会涉及，考场上也可以应对部分题目的暴力。 - 生成函数是用于刻画数列的组合工具，能够将很多复杂的组合问题赋以简洁的代数形式。同学们可以尝试用生成函数方法推导组合恒等式，体会代数手段的应用方式。请完成以下题目：P3746，P8558。 #### Part 5. 组合杂项 - 错排数。请完成以下题目：P4071。 - 斐波那契数列。请完成以下题目：P2020 - 使用矩阵乘法来优化递推数列。请完成以下题目：P1939 - Prufer 序，用来求解有标号无根树的计数问题。请完成以下题目：P2290。 - 矩阵树定理，用来计算生成树的方案数问题。请完成以下题目：P3317 - 斯特林数。请选择性完成以下题目：P4609，P6620，P8859。 - 置换群中的等价类计数。同学们需要先学习群、置换群、等价类这些基本的概念，然后学习用于求解置换群中等价类数量的Burnside引理，以及Burnside引理的一种特殊形式-Polya定理。请完成以下题目：P4980，P4727 - 学有余力的同学可以进一步了解贝尔数、伯努利数、分拆数、欧拉数的相关知识。 #### 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。 - 方差计算公式：$D(X) = E(X ^ 2) - E^2(X)$。 #### Part 3. 应用 在实际问题中，概率期望往往与动态规划等类似的结构相结合，需要根据题目设计状态，计算每个状态对应的概率期望。 - 状态间满足拓扑序的问题：可以按照拓扑序直接求解。请完成以下题目：P4284，P4206。 - 状态间不满足拓扑序的问题，一般通过高斯消元求解。请完成以下题目：P3211。特别地，对于特殊的矩阵，如关系图形成线性结构、树形结构时，可以采用主元法/待定系数法进行求解。请完成以下题目：P3750，P4457，P5643。 - 在图上随机游走问题时，我们有一种技巧是，用期望来求概率，请完成以下题目：CF113D