信息学竞赛中的数学知识简要梳理 信息学竞赛经常涉及一些数学知识
现在梳理一下
目录 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… ᵃᵅᵅᵅᵅ =ᵅ
n 种元素，每种有无限多个，选出r 个（可重复）的方案数（用夹棍法理解）： ᵄ = ᵃᵅ+ᵅ−1ᵅ−1 n 个不同元素，选出m 个，且每个都不相邻： ᵄ = ᵃᵅ−ᵅ+1ᵅ 1
2 母函数 母函数是一个函数，该函数有无限多项，且具有下面的形式： ᵃ(ᵆ) = ᵄ0 + ᵄ1ᵆ + ᵄ2ᵆ2 + ⋯ + ᵄᵅᵆᵅ + ⋯ = ∏ ᵄᵅᵆᵅ∞ᵅ=0 这样，一个母函数的的各项的系数就可以组成一个数列，并且任意一个数列都和母函
