《信息学竞赛中的数学知识小结》由会员分享，可在线阅读，更多相关《信息学竞赛中的数学知识小结（6页珍藏版）》请在金锄头文库上搜索。
1、-信息学竞赛中的数学知识简要梳理信息学竞赛经常涉及一些数学知识。现在梳理一下。目录1 组合数学：1.1 排列与组合1.2 母函数1.3 二项式定理1.4 容斥原理1.5 鸽巢原理1.6 群论特别是置换群1.7 Burnside引理与Polya定理2 线性代数：2.1 矩阵定义及运算2.2 高斯消元解线性方程组2.3 Matri*-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 数值运算
2、：5.1 Simpson启发式积分1 组合数学：1.1 排列与组合n个不同元素，其所有排列个个数：全排列n个不同元素，选出m个来做全排列，排列数：n个不同元素，选出m个的组合数：n个元素，有m种，第i种有ni个，每种则所有元素的排列数：n种元素，每种有无限多个，选出r个可重复的方案数用夹棍法理解：n个不同元素，选出m个，且每个都不相邻：1.2 母函数母函数是一个函数，该函数有无限多项，且具有下面的形式：这样，一个母函数的的各项的系数就可以组成一个数列，并且任意一个数列都和母函数一一对应，对数列的研究就可以用母函数来帮助了还需要牛顿二项式定理来推导*些特殊级数的有限多项式表示。1.3 二项式定理
3、1.4 容斥原理：思想是：统计所有的，减去多统计的，加上多减的，再减去多加的。由德摩根定理：所以：这样，我们不光可以用容斥定理来统计满足a，或满足b，或满足c的元素的个数，也可以用来统计不满足a并且不满足b并且不满足c的元素的个数。1.5 鸽巢原理：将n只鸽子放到n-1个巢中，至少有一个巢有大于一只鸽子。很显然的事情，但是用它的题目却不是则显然，需要我们不断的强化问题加更多自己的限制。我见过的用处是：给出n个自然数，找出其中一堆，使得他们的和为n的倍数。1.6 群论特别是置换群给定一个集合A和定义在上面的一种二元运算*，并满足：1、封闭性2、结合律3、存在单位元4、存在逆元则称A在运算*下成群
4、。置换群是一个群，它的集合A是由置换组成，运算*是置换的叠加。1.7 Burnside引理与Polya定理设存在一个集合S,并且集合中的元素s能被一个置换作用变成,并且该置换的逆置换能把s变成s。由置换群可以定义一个在S上的等价关系：如果能通过置换群中的置换变成，则a和b等价。可以证明这种关系满足：自反、对称、传递。然后置换群G就可以将S划分出很多等价类，上面两个定理就是用来统计有多少个等价类的。Burnside引理的内容是：设置换群为G,等价类的个数是N,置换a将s变成a(s)方括号表示如果条件成立，就是1，不成立为0.我们将这样一组满足a(s)=s的a和s成为一个不动点，即s在a的作用下不
5、变动。将其表示成文字语言就是：G将S划分出的等价类个数是G作用在S上的不动点个数除以置换数。Polya定理实际上就是告诉了我们一种求不动点个数的方法。具体见组合数学。2 线性代数：2.1 矩阵定义及运算：矩阵除了乘法还有加法，略2.2 高斯消元解线性方程组思想：先将系数矩阵变成一个上三角矩阵，然后从最后一行开场计算，开场回代。2.3 Matri*-Tree定理这个定理是用来算连通无向图的生成树个数的。算法的主要过程是先求出这个图的基尔霍夫矩阵度数矩阵减去关联矩阵。然后答案就是基尔霍夫矩阵的n-1阶余子式的行列式。一个方阵的行列式的值是：算出n个元素，要求每行每列都只有一个，然后将算出来的元素乘
6、起来，将选出来的元素的位置表示成n个二元组：(i,j)，这n个二元组组成一个置换，如果它是一个奇置换，将算出来的值乘以-1，否则不变。所有这样选法算出来的值的和就是行列式的值。对矩阵做一些简单的变换，行列式的值的变化也有一些规律，略。行列式的求法是将矩阵变成一个上三角矩阵行列式和原来一样，然后对角线的乘积就是答案。3 数论：3.1 扩展欧几里得求出中的。3.2 逆元求a在模m下的逆元。如果，则存在逆元，解方程：得到的*就是a在模m下的逆元。3.3 解模意义下方程形式一：对于形式一，将方程化简成:设，如果，则方程有解，否则无解。如果有解，即，可以证明：和同解先把模方程化简成二元等式，然后可以发现
7、前面方程的解也是后面方程的解，后面方程的解也是前面的解。然后解出这个方程。设初始解为，然后原始方程的d个解就是：形式二：如果这个方程组的所有m互质，则就是典型的中国剩余定理，如果不互质，就采用方程合并的思想通法。将两个方程合并：先将方程变形为：然后联立起来，解出，然后，然后上面的方程就等价于下面一个方程：一直这样合并，直到化简成只有一个方程，然后就完了。3.4 莫比乌斯反演先说积性函数，如果一个函数满足，当和是质数时，则称是积性函数，如果没有质数限制，上式依然成立，则称为完全积性函数。假设一个函数是积性函数，则可以定义其和函数:可以证明但我不知道，也是积性函数。再来看两个特殊的函数，和，即Mo
8、bius函数和Euler函数，其中可以证明这两个函数都是积性函数。下面是它们的和函数：Mobius反演就是根据和函数来求原函数，设的和函数是，则：这一堆东西有什么用呢？转换！如果我们在一堆求和式中出现了或者，则我们可以直接将他们看成和函数，用Mobius函数或Euler函数来表示，有时就可以到达化简的目的。3.5 Miller-Rabin素数测试对于一个数，如何判断它是否是质数？试除法要的时间复杂度，如果给我们一个64位无符号数，让我们判断，则这个方法就不行了。Miller-Rabin算法是一种随机算法，但只要随机次数一大，正确概率就很大很大了。算法要用到两个定理：定理一费马小定理：如果是质数
9、，则对于任何正整数有：定理二：如果是一个奇素数，则的解是。我们需要利用这两个定理的逆否命题，即如果不这样，就不是素数。所以如果算法返回否，则该数一定不是素数，如果返回是，则有可能是素数。算法流程：1、 设判定的数为，特判一下，假设是大于2的奇数则继续。2、 分解指数，其中尽量大。3、 随机取一个正整数作为底数。4、 依次计算底数为，的幂在模下的的值，将这列数看成一个数列，最后一项就是。从第二项开场，如果*一项的值是1，判断它前面那一项的值是不是模意义下的1或-1，如果不是，根据定理二，返回否。5、 看最后一项为哪一项不是1，如果不是，根据定理一，返回否。执行810次根本就可以保证正确性了。3.
10、6 Pollard-Rho 因子分解这里只说一下大概步骤思想？，参加要分解，我们维护两个序列：其中从头开场计算第一个序列，每计算完成一项，看其中和是最新算出来的项是否是的非平凡因子，当,它的复杂度和正确性分析请看算法导论。3.7 BSGS 离散对数问题：给定正整数，求满足的。我们知道，意思是有一个长度为的循环，我们可以只枚举长度为的一段就可以知道解或者无解。但是枚举依旧吃不消，则我们可以分块算，简单来说，就是先算长度为的那个序列个前项，将它们放到一个hash表中，然后每次计算的值，计算它的逆，再计算逆与的乘积，看hash表中有没有算出来的这个值，如果有，就找到了，找完都没有那就真的没有了。原理
11、就是：4 博弈论：4.1 组合游戏一类组合游戏的定义：1、 两位游戏者轮流操作2、 游戏状态集有限，且不管怎么走都不会出现以前出现过的状态。3、 谁不能操作谁输。4.2 SG函数和SG定理对于一个上面这种游戏，设一个状态为，它的SG函数值定义为：，其中S是的所有后继状态组成的集合，是不在集合中状态的SG值内的最小非负值。然后状态必败当且仅当它的SG函数值为0.SG定理：一个组合游戏的SG和是子游戏的SG的Nim和异或和。5 数值运算：5.1 Simpson 启发式积分有时我们需要求一些图形的面积，当东西很不规则时，就不好做，这时，我们可以将所有东西都往下压，即计算每个对应的高度所有东西的并在该位置的长度，然后问题转化为求一个曲线下面的面积，然后这不就是积分吗？然后计算机不是处理离散对象的吗？积分好似很难搞定。然后就有了这东西，设要算函数在区间的值：当区间取得越短，面积就越准确。参考资料：NOI国家集训队论文组合数学算法导论算法竞赛入门经典训练指南新编实用算法分析与程序设计本文目的主要是自己的知识梳理，写完后感觉对很多东西的认识更清晰了PS:感觉微软的数学公式编辑器很弄出来的东西很漂亮。By Idy002 2/26/2015. z.
