信息奥赛中的数学方法.ppt

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