信息学竞赛中的数学方法清华大学计算机系 胡泽聪目录l 基础数论l模意义下的运算l费马小定理、欧拉定理与乘法逆元l快速幂与快速乘法l辗转相除法与高精度GCDl线性同余方程与拓展欧几里得算法l筛法与质因数分解l 组合数学入门l排列与组合l常用公式l简单的组合数取模l常用数列l容斥原理与禁位排列l 位运算及bitset基础数论BASIC NUMBER THEORY基本概念带余除法模数、取模同余因子互质最大公因数模意义下的运算 很多题目的基础 加减乘法在模意义下封闭 除法则不同费马小定理欧拉定理乘法逆元一些大质数快速幂快速幂快速幂：代码快速乘法最大公因数（GCD）更相减损术辗转相除法辗转相除法：代码高精度加减乘法高精度除法高精度GCD线性同余方程拓展欧几里得算法拓展欧几里得算法拓展欧几里得算法拓展欧几里得算法：代码求解线性同余方程分解质因数枚举因子筛法筛法基础数论：例题BASIC NUMBER THEORY: EXAMPLESNOIP2012 D2T1同余方程题面题解 拓展欧几里得的直接应用。 也可以直接算逆元。POJ1061青蛙的约会题面题解HDU2824The Euler Function题意题解POJ2480Longges Problem题意题解SGU106The Equation题意题解进一步了解组合数学入门INTRODUCTORY COMBINATORICS基本计数原理加法原理乘法原理减法原理计数问题 统计满足某些条件的物体的个数。 例：求项链的本质不同的染色方案数求图的不同生成树的个数 答案通常很大，需要取模输出。 两个要点： 不重不重、不漏不漏排列与组合Pascal公式常用公式常用公式常用公式证明的两种方式1.组合学推理2.数学推导尝试一下证明模意义下的组合数Catalan数列Catalan数列Bell数列容斥原理错位排列禁位排列组合数学入门：例题INTRODUCTORY COMBINATORICS: EXAMPLES一道数学题题面题解POJ3421X-factor Chains题意题解URAL1860Fiborial题面题解POJ3088Push Button Lock题面题解无名试题1题面题解组合数学习题8.5题面题解SKI题面题解进一步了解位运算与bitsetBITWISE OPERATIONS AND STD:BITSET位运算集合的二进制表示 适用于全集大小比较小（通常在32以内）的情况。 用一个unsigned int表示一个子集。 二进制位为1代表子集中有这个元素，0代表没有。判断元素是否存在：加入元素：删除元素：改变元素状态：（如果存在则删除，否则加入）与其他集合的交并异或集合的补：与其他集合的差：集合操作枚举子集std:bitsetstd:bitset用例自己实现bitset 内部为unsigned int数组。 与或非异或：对所有数字进行位运算 左移右移：自己实现bitsetbitset的简单应用 状态压缩动态规划（通常用单个int表示状态，偶尔用得到ll）。 存储值为bool类型的动态规划，如判断背包是否可行。 以0-1背包为例：终THE END