信息学竞赛中的数学知识简要梳理 信息学竞赛经常涉及一些数学知识。现在梳理一下。 目录 1 组合数学： 1.1 排列与组合 1.2 母函数 1.3 二项式定理 1.4 容斥原理 1.5 鸽巢原理 1.6 群论（特别是置换群） 1.7 Burnside 引理与 Polya 定理 2 线性代数： 2.1 矩阵定义及运算 2.2 高斯消元解线性方程组 2.3 Matrix-Tree 定理 3 数论： 3.1 扩展欧几里得 3.2 逆元 3.3 解模意义下方程 3.4 莫比乌斯反演 3.5 Miller-Rabin 素数测试 3.6 Pollard-Rho 因子分解 3.7 BSGS 离散对数 4 博弈论： 4.1 组合游戏 4.2 GS 函数和 GS 定理 5 数值运算： 5.1 Simpson 启发式积分 1 组合数学： 1.1 排列与组合 n 个不同元素，其所有排列个个数：全排列 ᵄᵅ = ᵅ! n 个不同元素，选出m 个来做全排列，排列数： ᵄ ᵅᵅ = ᵅ(ᵅ − 1)(ᵅ− 2) … (ᵅ − ᵅ+ 1) n 个不同元素，选出m 个的组合数： ᵃᵅᵅ =ᵅ!ᵅ!(ᵅ− ᵅ)! n 个元素，有m 种，第i 种有ni 个，每种则所有元素的排列数： ᵄ = ᵃᵅᵅ1ᵃᵅ−ᵅ1ᵅ1ᵃᵅ−ᵅ1−ᵅ2ᵅ1… ᵃᵅᵅᵅᵅ =ᵅ!ᵅ1! ᵅ2! ᵅ3! ᵅ4! … ᵅᵅ! n 种元素，每种有无限多个，选出r 个（可重复）的方案数（用夹棍法理解）： ᵄ = ᵃᵅ+ᵅ−1ᵅ−1 n 个不同元素，选出m 个，且每个都不相邻： ᵄ = ᵃᵅ−ᵅ+1ᵅ 1.2 母函数 母函数是一个函数，该函数有无限多项，且具有下面的形式： ᵃ(ᵆ) = ᵄ0 + ᵄ1ᵆ + ᵄ2ᵆ2 + ⋯ + ᵄᵅᵆᵅ + ⋯ = ∏ ᵄᵅᵆᵅ∞ᵅ=0 这样，一个母函数的的各项的系数就可以组成一个数列，并且任意一个数列都和母函数一一对应，对数列的研究就可以用母函数来帮忙了（还需要牛顿二项式定理来推导某些特殊级数的有限多项式表示）。 1.3 二项式定理 1.4 容斥原理： |⋃ ᵃᵅ| = ∑|ᵃᵅ| − ∑|ᵃᵅ ∩ ᵃᵅ| + ∑|ᵃᵅ ∩ ᵃᵅ ∩ ᵃᵅ| … 思想是：“统计所有的，减去多统计的，加上多减的，再减去多加的… ”。 由德摩根定理： ⋃ ᵃᵅ̅̅̅̅̅̅̅̅ = ⋂ᵃᵅ̅ 所以： ᵄ = |⋃ ᵃᵅ| + |⋃ ᵃᵅ̅̅̅̅̅̅̅̅| = |⋃ ᵃᵅ| + |⋂ᵃᵅ̅ | |⋂ᵃᵅ̅ | = ᵄ − |⋃ ᵃᵅ| 这样，我们不光可以用容斥定理来统计“满足 a，或满足 b，或满足 c… ”的元素的个数，也可以用来统计“不满足 a 并且不满足 ...
