NOIP 数学专题：数论、组合数学、概率期望全部模板

数学是信息学竞赛的"隐藏关卡"，很多题目到最后都是数学问题。

一、数论基础

• 素数筛：埃氏筛 O(n log log n)、欧拉筛 O(n)


• 快速幂：O(log n)


• 最大公约数：欧几里得算法（辗转相除法）


• 扩展欧几里得：求 ax + by = gcd(a, b) 的一组整数解


• 费马小定理与欧拉定理


• 乘法逆元的三种求法（费马、扩欧、递推）


• 中国剩余定理（CRT / EXCRT）


• 卢卡斯定理（组合数取模，模数为质数）

• 排列数、组合数的计算


• 二项式系数性质（杨辉三角递推）


• 容斥原理


• 卡特兰数（括号序列、出栈序列数）


• 斯特林数（第一类、第二类）


• 错排公式


• Burnside 引理 / Polya 定理（群论计数）

• 高斯消元：解线性方程组 O(n³)


• 矩阵快速幂：加速递推


• 行列式与 Matrix-Tree 定理（生成树计数）

• 期望的线性性（最重要！）


• 概率 DP


• 期望 DP


• 条件概率与全概率公式

• Nim 游戏与 SG 函数


• 有向图游戏


• 巴什博奕、威佐夫博奕

• 快速幂 + 逆元：洛谷 P1226


• CRT：洛谷 P1495


• 高斯消元：洛谷 P3389


• 期望 DP：洛谷 P4316