信息学竞赛中的数学知识小结7页.docx

信息学竞赛中的数学知识简要梳理信息学竞赛经常涉及一些数学知识。现在梳理一下。目录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个不同元素，其所有排列个个数：全排列Pn=n!n个不同元素，选出m个来做全排列，排列数：P nm=nn-1n-2(n-m+