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

单击此处编辑母版标题样式,单击此处编辑母版文本样式,a,二级,三级,四级,五级,3,#,信息学竞赛中的数学方法,清华大学计算机系 胡泽聪,1,3,目录,基础数论,模意义下的运算,费马小定理、欧拉定理与乘法逆元,快速幂与快速乘法,辗转相除法与高精度,GCD,线性同余方程与拓展欧几里得算法,筛法与质因数分解,组合数学入门,排列与组合,常用公式,简单的组合数取模,常用数列,容斥原理与禁位排列,位运算及,bitset,2,12/3/2024,基础数论,Basic,Number,Theory,3,12/3/2024,基本概念,带余除法,模数、取模,同余,因子,互质,最大公因数,4,12/3/2024,模意义下的运算,很多题目的基础,加减乘法在模意义下封闭,除法则不同,5,12/3/2024,费马小定理,要求,为质数，且,不是,的倍数。特别地，,可以为,。,证明思路：,。,6,12/3/2024,欧拉定理,要求,与,互质。,为欧拉函数，定义为小于等于,且与,互质的数的个数。,设,，则,。,对于质数而言，,。,7,12/3/2024,乘法逆元,除法是乘法的逆运算。有,。,由欧拉定理，,。,则,为,在模,意义下的乘法逆元，等价于,，记作,。,当然，前提是,和,互质。,8,12/3/2024,一些大质数,（不常用）,奇怪的生日,9,12/3/2024,快速幂,由于模数通常很大，求逆元需要算的幂次也就很大。,朴素的,做法无法接受。,10,12/3/2024,快速幂,考虑,，将,按二进制位分解。,如果我们知道,可以把,的所有为,的二进制位对应的次幂相乘得到,。,复杂度,。,11,12/3/2024,快速幂：代码,12,12/3/2024,快速乘法,有时模数实在太大，以至于两数相乘无法用,long,long,表示。,写高精度乘法显然不划算。,类似快速幂，处理出,。,每次只要乘,，一般来说可以接受。,要是还存不下就没办法了。,13,12/3/2024,最大公因数（,GCD,）,Greatest Common Divisor,，记作,。,一些性质：,14,12/3/2024,更相减损术,利用,。用大数减小数，得到新的一对,和,，并重复以上过程。,复杂度无法得到保证。,15,12/3/2024,辗转相除法,假设,，那么更相减损术会一直使,，直到,。,这其实就是,。,于是就得到了辗转相除法。,复杂度为,。,16,12/3/2024,辗转相除法：代码,17,12/3/2024,高精度加减乘法,用字符串表示数字，模拟竖式计算。,加减法复杂度,，乘法复杂度,，,为数字位数。,常用优化：压位。,18,12/3/2024,高精度除法,类似竖式除法。,在除数末尾补尽量多的,，使得其恰好小于被除数；,进行数次高精度减法，直到被除数小于除数；,令商加上减法次数；,如果除数末尾还有之前补上的,，则除数除以,，商乘以,，跳转到第,2,步；,剩下的被除数即为余数。,复杂度,。,19,12/3/2024,高精度,GCD,辗转相除？,可能进行,次除法运算，高精度除法太慢。,考虑更相减损，加入一些优化：,如果,和,都是偶数，直接令两数除以,，并令,GCD,乘以,；,如果,和,一奇一偶，则除去偶数的所有,的因子；,如果,和,都是奇数，则令大数减小数，此时必然得到一个偶数。,复杂度如何？,每两步就能令一个数除以,2,，故减法次数为,。,总复杂度,。,20,12/3/2024,线性同余方程,形如,，求,的值。,一些性质：,如果,，则方程有且仅有一个解,；,方程有解,，且解数为,。,而同余方程与不定方程,同解21,12/3/2024,拓展欧几里得算法,拓展欧几里得算法在求出,的同时，还能顺带解出不定方程,的一组解。,这个不定方程等价于线性同余方程,，所以必然有解。,22,12/3/2024,拓展欧几里得算法,考虑,的辗转相除过程：,得到,求出,GCD,之后，将整个过程倒过来：,23,12/3/2024,拓展欧几里得算法,求出,GCD,之后，将整个过程倒过来：,依次带入得：,解得,。,24,12/3/2024,拓展欧几里得算法：代码,25,12/3/2024,求解线性同余方程,之前说到同余方程与不定方程,同解。,移项得,，而,令,使用拓展欧几里得算法求解,的解,；,则原方程的解为,、,。,26,12/3/2024,分解质因数,一个数,最多有一个大于,的质因子。,枚举所有不超过,的质数并试除；,如果剩下的,，那么这也是一个质因子。,复杂度为,。,27,12/3/2024,枚举因子,一个数,的每个大于等于,的因子,必然对应一个小于等于,的因子,。,算法和分解质因数基本一样。,因子个数的上界,，但实际上达不到这个上界。,28,12/3/2024,筛法,预处理,的所有质数。,是质数；,对于每个质数，枚举其不超过,的所有倍数，标记为合数。,就这么简单。,复杂度为,。,（调和级数,）,29,12/3/2024,筛法,我们还可以顺便处理出,内每个数的最小值因子。,有了这个信息之后，便可以在,的时间内分解质因数。,30,12/3/2024,基础数论：例题,Basic Number Theory:Examples,31,12/3/2024,NOIP2012,D2T1,同余方程,题面,求,的最小正整数解。,。,题解,拓展欧几里得的直接应用。,也可以直接算逆元。,32,12/3/2024,POJ1061,青蛙的约会,题面,假设赤道是长度为,的数轴，坐标为,的整数，跳过,之后会从,一侧跳出来。,两只青蛙分别在,和,的位置，每次分别可以跳,和,格。问最少跳几次之后，两只青蛙会相遇。,。,题解,其实就是求关于,的同余方程,的最小非负整数解。,化一下即,。判断是否有解之后解之即可。,33,12/3/2024,HDU2824,The Euler Function,题意,求,。,。,（此处为原题削弱版）,题解,用筛法处理出每个数的最小质因子，并利用它来在,时间内计算,的值。,34,12/3/2024,POJ2480Longges Problem,题意,求,。,。,题解,转换思路：,的值肯定是,的因子。设其为,。,那有多少,满足,？,同时除以,，即问有多少,满足,？,而这个个数就是,。,所以答案就是,。,注意在求,时应利用,的质因子分解结果。总复杂度约为,。,35,12/3/2024,SGU106The Equation,题意,求,在,且,的条件下有多少组解。,所有数字绝对值均不超过,。,题解,先考虑几种特殊情况：,；,（无解）；,和,中有且仅有一个,；,（无解）。,对于剩下的情况，先将,变为非负数，并求出一组可行解,。,之后便是求有多少,满足,且,，直接做除法取整即可。,36,12/3/2024,进一步了解,中国剩余定理，用于求解线性同余方程组,线性筛法（,Eratosthenes,筛法），即复杂度为,的筛法,Miller-Rabin,素数判定法，复杂度为,的概率算法,离散对数，即求满足,的,大步小步算法（,Baby-step-giant-step,，,BSGS,），用于求解离散对数,37,12/3/2024,组合数学入门,Introductory,Combinatorics,3812/3/2024,基本计数原理,加法原理,乘法原理,减法原理,39,12/3/2024,计数问题,统计满足某些条件的物体的个数。,例：,求项链的本质不同的染色方案数,求图的不同生成树的个数,答案通常很大，需要取模输出。,两个要点：,不重,、,不漏,40,12/3/2024,排列与组合,个人排成一排的方案数：,从,个人中选出,个的方案数：,也就是组合数，记作,或者,。,41,12/3/2024,Pascal,公式,即考虑最后一个人选还是不选。,平日所说的杨辉三角就是这个东西。,42,12/3/2024,常用公式,多重集,的排列：,二项式定理：,43,12/3/2024,常用公式,从,的网格的左上角走到右下角，每次只能向右或者向下走，行走路径的方案数：,方程,的非负整数解数：,44,12/3/2024,常用公式,45,12/3/2024,证明的两种方式,组合学推理,数学推导,46,12/3/2024,尝试一下证明,范德蒙德（,Vandermonde,）卷积,47,12/3/2024,模意义下的组合数,直接利用,Pascal,公式,对模数没有要求,定义直接算逆元,较小,模数为质数,预处理阶乘逆元,模数为质数,48,12/3/2024,Catalan,数列,卡特兰数,其含义为：,个,和,个,构成一个序列,，且任意前缀和,的方案数。,证明：,所有序列方案为,；,不合法序列中存在一个最小的位置,，使得,；,由于,最小，因此,且,；,将,变为相反数，此时序列有,个,和,个,；,而不合法序列可以和有,个,和,个,的序列一一对应；,故方案数为,。,49,12/3/2024,Catalan,数列,卡特兰数的另一种表达方式是：,所以卡特兰数还是二叉树的方案数。,50,12/3/2024,Bell,数列,贝尔数,为将,个不同元素划分成任意份的方案数。,一般不需要计算，只是用来估计复杂度。,51,12/3/2024,容斥原理,集合的补：,设,为集合,中具有一些性质的元素的集合，则,52,12/3/2024,错位排列,满足,不在第,位的排列，记为,。,递推公式：,53,12/3/2024,禁位排列,的棋盘上摆放,个车，互相不能攻击，方案数为,。,如果有不能摆放的位置呢？,求出“至少有”,个车处于禁位上的方案数，容斥原理。,（将“某个禁位上有车”看做一种属性）,54,12/3/2024,组合数学入门：例题,Introductory,Combinatorics:Examples,55,12/3/2024,一道数学题,题面,一个集合的子集个数为,，那一个集合的所有子集的子集个数之和是多少？,题解,一个集合的大小为,的子集个数为,。,那么答案为,56,12/3/2024,POJ3421X-factor Chains,题意,给定正整数,，称其因数链为序列,，满足,，且,。,求,的最长因数链长度与方案数。,。,题解,对,做质因数分解，显然最长的方案一定是每次除以一个质因子。,而方案数就是质因子的多重集排列。,57,12/3/2024,URAL1860Fiborial,题面,定义序列,如下：,求,的因子数。,。,题解,其实这题更多程度上是数论题。,分析得出,。,利用筛法预处理，求出,的质因数分解。,假设各个质因子的次数为,，因子个数是多少？,是,。,58,12/3/2024,POJ3088Push Button Lock,题面,定义一种序列如下：每个位置上是一个,的子集，任意两个位置上的集合交为空。两个序列不同当且仅当长度不同或者某个位置上的集合不同。,求这样的序列的方案数。,。多组询问。,（此处为原题加强版）,题解,枚举序列中子集大小之和,及序列长度,。,现在要求的就是将这,个数字分成,份的方案数。,DP,解决。,答案即为,DP,求出来的其实是第二类斯特林（,Stirling,）数。,59,12/3/2024,无名试题,1,题面,集合,中有,个元素，你需要选出,的,个子集，满足这些子集的交集为空集。,求选择方案数。,。,题解,每个元素分开考虑。,这个元素不能处于所有,个子集中，但其他任意分配方案都可行。,所以这个元素的分配方案数为,。,所以答案为,。,60,12/3/2024,组合数学,习题,8.5,题面,个,和,个,，构成一个序列。求前缀和均,的序列的方案数。,。,题解,的情况即为卡特兰数，,的分析类似。,答案为：,61,12/3/2024,SKI,题面,的网格，每个格子有一个高度。一个人从任意网格开始滑雪，并在任意一个网格结束。只能从较高的网格滑向较低的网格。,问所有路径长度的,次方的和。,，,。,所有相邻网格高度不同。,题解,先考虑,的情况，即为普通的,DP,。,假设我们有上一个状态的,次方的答案，怎么转移到下一个状态？,二项式定理！,62,12/3/2024,进一步了解,棋盘多项式，另一种求禁位排列的方法,矩阵乘法，可以快速计算一些简单的递推公式,快速阶乘，快速计算,，其中,为质数；可以用来计算大组合数取模，并可以配合中国剩余定理使用,置换、,Burnside,引理与,Plya,计数法，用于计算考虑同构时的本质不同方案数,Prfer,序列，用于唯一描述树的形态，并可用于计算满足一定条件的树的方案数,63,12/3/2024,位运算与,bitset,Bitwise Operations and std:bitset,64,12/3/2024,位运算,65,12/3/2024,集合的二进制表示,适用于全集大小比较小（通常在,32,以内）的情况。,用一个,unsigned,int,表示一个子集。,二进制位为,1,代表子集中有这个元素，,0,代表没有。,66,12/3/2024,判断元素是否存在：,加入元素：,删除元素：,改变元素状态：（如果存在则删除，否则加入）,与其他集合的交并异或,集合的补：,与其他集合的差：,集合操作,67,12/3/2024,枚举子集,68,12/3/2024,std:bitset,二进制方式存储集合，支持任意位数。,支持上述所有集合操作。,对整个集合的操作时间复杂度均为,。,69,12/3/2024,std:bitset,用例,70,12/3/2024,自己实现,bitset,内部为,unsigned,int,数组。,与或非异或：对所有数字进行位运算,左移右移：,71,12/3/2024,自己实现,bitset,统计,1,的个数：,朴素,方法,预处理,+,分段查表,分治,72,12/3/2024,bitset,的简单应用,状态压缩动态规划（通常用单个,int,表示状态，偶尔用得到,ll,）。,存储值为,bool,类型的动态规划，如判断背包是否可行。,以,0-1,背包为例：,73,12/3/2024,终,The End,74,12/3/2024,