信息学竞赛中的数学知识小结

信息学竞赛中的数学知识简要梳理信息学竞赛经常涉及一些数学知识。现在梳理一下。目录1组合数学：1.1排列与组合1.2母函数1.3二项式定理1.4容斥原理1.5鸽巢原理1.6群论（特别是置换群）1.7Burnside引理与Polya定理2线性代数：2.1矩阵定义及运算2.2高斯消元解线性方程组2.3Matrix-Tree定理3数论：3.1扩展欧几里得3.2逆元3.3解模意义下方程3.4莫比乌斯反演3.5Miller-Rabin素数测试3.6Pollard-Rho因子分解3.7BSGS离散对数4博弈论：4.1组合游戏4.2GS函数和GS定理5数值运算：5.1Simpson启发式积分1组合数学：1.1排列与组合n个不同元素，其所有排列个个数：全排列𝑃𝑛=𝑛!n个不同元素，选出m个来做全排列，排列数：𝑃𝑛𝑚=𝑛(𝑛−1)(𝑛−2)…(𝑛−𝑚+1)n个不同元素，选出m个的组合数：𝐶𝑛𝑚=𝑛!𝑚!(𝑛−𝑚)!n个元素，有m种，第i种有ni个，每种则所有元素的排列数：𝑃=𝐶𝑛𝑛1𝐶𝑛−𝑛1𝑛1𝐶𝑛−𝑛1−𝑛2𝑛1…𝐶𝑛𝑚𝑛𝑚=𝑛!𝑛1!𝑛2!𝑛3!𝑛4!…𝑛𝑚!n种元素，每种有无限多个，选出r个（可重复）的方案数（用夹棍法理解）：𝑁=𝐶𝑛+𝑟−1𝑛−1n个不同元素，选出m个，且每个都不相邻：𝑁=𝐶𝑛−𝑚+1𝑚1.2母函数母函数是一个函数，该函数有无限多项，且具有下面的形式：𝐺(𝑥)=𝑎0+𝑎1𝑥+𝑎2𝑥2+⋯+𝑎𝑖𝑥𝑖+⋯=∏𝑎𝑖𝑥𝑖∞𝑖=0这样，一个母函数的的各项的系数就可以组成一个数列，并且任意一个数列都和母函数一一对应，对数列的研究就可以用母函数来帮忙了（还需要牛顿二项式定理来推导某些特殊级数的有限多项式表示）。1.3二项式定理1.4容斥原理：|⋃𝐴𝑖|=∑|𝐴𝑖|−∑|𝐴𝑖∩𝐴𝑗|+∑|𝐴𝑖∩𝐴𝑗∩𝐴𝑘|…思想是：“统计所有的，减去多统计的，加上多减的，再减去多加的…”。由德摩根定理：⋃𝐴𝑖̅̅̅̅̅̅̅̅=⋂𝐴𝑖̅所以：𝑁=|⋃𝐴𝑖|+|⋃𝐴𝑖̅̅̅̅̅̅̅̅|=|⋃𝐴𝑖|+|⋂𝐴𝑖̅||⋂𝐴𝑖̅|=𝑁−|⋃𝐴𝑖|这样，我们不光可以用容斥定理来统计“满足a，或满足b，或满足c…”的元素的个数，也可以用来统计“不满足a并且不满足b并且不满足c”的元素的个数。1.5鸽巢原理：将n只鸽子放到n-1个巢中，至少有一个巢有大于一只鸽子。很显然的事情，但是用它的题目却不是那么显然，需要我们不断的强化问题（加更多自己的限制）。我见过的用处是：给出n个自然数，找出其中一堆，使得他们的和为n的倍数。1.6群论（特别是置换群）给定一个集合A和定义在上面的一种二元运算“*”，并满足：1、封闭性2、结合律3、存在单位元4、存在逆元那么称A在运算“*”下成群。置换群是一个群，它的集合A是由置换组成，运算“*”是置换的叠加。1.7Burnside引理与Polya定理设存在一个集合S,并且集合中的元素s能被一个置换作用变成s′∈S,并且该置换的逆置换能把s’变成s。由置换群可以定义一个在S上的等价关系：如果a∈S能通过置换群中的置换变成b∈S，那么a和b等价。可以证明这种关系满足：自反、对称、传递。然后置换群G就可以将S划分出很多等价类，上面两个定理就是用来统计有多少个等价类的。Burnside引理的内容是：设置换群为G,等价类的个数是N,置换a将s变成a(s)|𝐺|𝑁=∑∑[𝑠=𝑎(𝑠)]𝑠∈𝑆𝑎∈𝐴（方括号表示如果条件成立，就是1，不成立为0.）我们将这样一组满足a(s)=s的a和s成为一个不动点，即s在a的作用下不变动。将其表示成文字语言就是：“G将S划分出的等价类个数是G作用在S上的不动点个数除以置换数”。Polya定理实际上就是告诉了我们一种求不动点个数的方法。具体见《组合数学》。2线性代数：2.1矩阵定义及运算：（矩阵除了乘法还有加法，略）2.2高斯消元解线性方程组思想：先将系数矩阵变成一个上三角矩阵，然后从最后一行开始计算，开始回代。2.3Matrix-Tree定理这个定理是用来算连通无向图的生成树个数的。算法的主要过程是先求出这个图的基尔霍夫矩阵（度数矩阵减去关联矩阵）。然后答案就是基尔霍夫矩阵的n-1阶余子式的行列式。一个方阵的行列式的值是：算出n个元素，要求每行每列都只有一个，然后将算出来的元素乘起来，将选出来的元素的位置表示成n个二元组：(i,j)，这n个二元组组成一个置换，如果它是一个奇置换，将算出来的值乘以-1，否则不变。所有这样选法算出来的值的和就是行列式的值。对矩阵做一些简单的变换，行列式的值的变化也有一些规律，略。行列式的求法是将矩阵变成一个上三角矩阵（行列式和原来一样），然后对角线的乘积就是答案。3数论：3.1扩展欧几里得求出𝑎𝑥+𝑏𝑦=𝑔𝑐𝑑(𝑎,𝑏)中的𝑥,𝑦和𝑔𝑐𝑑(𝑎,𝑏)。3.2逆元求a在模m下的逆元。如果𝑔𝑐𝑑(𝑎,𝑚)=1，则存在逆元，解方程：𝑎𝑥+𝑚𝑦=𝑔𝑐𝑑(𝑎,𝑚)得到的x就是a在模m下的逆元。3.3解模意义下方程形式一：𝑎𝑥≡𝑏(𝑚𝑜𝑑𝑚)对于形式一，将方程化简成:𝑎𝑥−𝑚𝑦=𝑏设d=gcd(a,m)，如果d|b，则方程有解，否则无解。如果有解，即d|b，可以证明：𝑎𝑥≡𝑏(𝑚𝑜𝑑𝑚)和𝑎𝑑𝑥≡𝑏𝑑(𝑚𝑜𝑑𝑚𝑑)同解（先把模方程化简成二元等式，然后可以发现前面方程的解也是后面方程的解，后面方程的解也是前面的解）。然后解出这个方程（因为𝑎/𝑑和𝑚/𝑑互质，𝑎/𝑑∗𝑥=1(𝑚𝑜𝑑𝑚/𝑑)必定存在解，将解乘以𝑏/𝑑就是该方程的解）。设初始解为𝑥0，然后原始方程的d个解就是：𝑥𝑖=𝑥0+𝑖𝑚𝑑,𝑖∈[0,d−1]形式二：𝑥≡𝑏𝑖(𝑚𝑜𝑑𝑚𝑖)如果这个方程组的所有m互质，那么就是典型的中国剩余定理，如果不互质，就采用方程合并的思想（通法）。将两个方程合并：𝑥≡𝑏1(𝑚𝑜𝑑𝑚1)𝑥≡𝑏2(𝑚𝑜𝑑𝑚2)先将方程变形为：𝑥≡𝑏1+𝑚1𝑦𝑥≡𝑏2+𝑚2𝑧然后联立起来，解出𝑦，然后x=b1+m1y，然后上面的方程就等价于下面一个方程：𝑥≡𝑏12(𝑚𝑜𝑑𝑚12),𝑏12=𝑏1+𝑚1𝑦,𝑚12=𝑙𝑐𝑚(𝑚1,𝑚2)一直这样合并，直到化简成只有一个方程，然后就完了。3.4莫比乌斯反演先说积性函数，如果一个函数f(x)满足，当𝑥和𝑦是质数时，𝑓(𝑥𝑦)=𝑓(𝑥)𝑓(𝑦)则称𝑓(𝑥)是积性函数，如果没有质数限制，上式依然成立，则称𝑓(𝑥)为完全积性函数。若一个函数𝑓(𝑥)是积性函数，那么可以定义其和函数𝑔(𝑥):𝑔(𝑥)=∑𝑓(𝑥)𝑑|𝑥可以证明（但我不知道），𝑔(𝑥)也是积性函数。再来看两个特殊的函数，μ(x)和φ(x)，即Mobius函数和Euler函数，其中𝜇(𝑥)={0如果𝑥存在平方约数，否则(−1)𝑟𝑟=𝑥的质因数个数φ(x)=∑[gcd(i,x)==1]1≤i≤x可以证明这两个函数都是积性函数。下面是它们的和函数：𝑓(𝑥)=[𝑥=1]=∑𝜇(𝑥)𝑑|𝑥𝑓(𝑥)=𝑥=∑𝜑(𝑥)𝑑|𝑥Mobius反演就是根据和函数来求原函数，设𝑓(𝑥)的和函数是𝑔(𝑥)，那么：𝑓(𝑥)=∑𝜇(𝑑)𝑔(𝑥𝑑)𝑑|𝑥这一堆东西有什么用呢？转换！如果我们在一堆求和式中出现了[𝑥==1]或者𝑥，那么我们可以直接将他们看成和函数，用Mobius函数或Euler函数来表示，有时就可以达到化简的目的。3.5Miller-Rabin素数测试对于一个数𝑥，如何判断它是否是质数？试除法要𝑂(√𝑥)的时间复杂度，如果给我们一个64位无符号数，让我们判断，那么这个方法就不行了。Miller-Rabin算法是一种随机算法，但只要随机次数一大，正确概率就很大很大了。算法要用到两个定理：定理一（费马小定理）：如果𝑝是质数，那么对于任何正整数𝑎有：𝑎𝑝−1≡1(𝑚𝑜𝑑𝑝)定理二：如果𝑝是一个奇素数，那么𝑥2≡1(𝑚𝑜𝑑𝑝)的解是±1。我们需要利用这两个定理的逆否命题，即“如果不这样，就不是素数”。所以如果算法返回否，那么该数一定不是素数，如果返回是，则有可能是素数。算法流程：1、设判定的数为𝑥，特判一下，若𝑥是大于2的奇数则继续。2、分解指数𝑥−1=𝑢2𝑡，其中𝑡尽量大。3、随机取一个正整数𝑎作为底数。4、依次计算底数为𝑎，指数为u,2u,2∗2u,2∗2∗2u…，的幂在模𝑥下的的值，将这列数看成一个数列，最后一项就是𝑥。从第二项开始，如果某一项的值是1，判断它前面那一项的值是不是模意义下的1或-1，如果不是，根据定理二，返回否。5、看最后一项是不是1，如果不是，根据定理一，返回否。执行8~10次基本就可以保证正确性了。3.6Pollard-Rho因子分解这里只说一下大概步骤（思想？），加入要分解𝑛，我们维护两个序列：𝑥1,𝑥2,𝑥3,𝑥4,𝑥5,𝑥6,…𝑦1,𝑦2,𝑦3,𝑦4,𝑦5,…其中𝑥𝑖=𝑓(𝑥𝑖−1)(𝑥1=𝑟𝑎𝑛𝑑𝑜𝑚(0,𝑛−1))yi=x2i−1从头开始计算第一个序列，每计算完成一项，看𝑔𝑐𝑑(𝑥−𝑦,𝑛)（其中𝑥和𝑦是最新算出来的项）是否是𝑛的非平凡因子，当𝑥==𝑦时退出,它的复杂度和正确性分析请看《算法导论》。3.7BSGS离散对数问题：给定正整数𝑎,𝑏,𝑚，求满足𝑎𝑥≡𝑏(𝑚𝑜𝑑𝑚)的𝑥。我们知道𝑎𝜑(𝑚)≡1(𝑚𝑜𝑑𝑚)，意思是a0,a1,a2,a3,…有一个长度为𝜑(𝑚)的循环，我们可以只枚举长度为𝜑(𝑚)的一段就可以知道解或者无解。但是枚举依旧吃不消，那么我们可以分块算，简单来说，就是先算长度为𝜑(𝑚)的那个序列个前𝑙𝑒𝑛项，将它们放到一个hash表中，然后每次计算𝑎𝑖∗𝑙𝑒𝑛的值，计算它的逆，再计算逆与𝑏的乘积，看hash表中有没有算出来的这个值，如果有，就找到了，找完都没有那就真的没有了。原理就是：𝑎𝑥≡𝑎𝑖∗𝑙𝑒𝑛+𝑗≡𝑏(𝑚𝑜𝑑𝑚)𝑎𝑖∗𝑙𝑒𝑛+𝑗(𝑎𝑖∗𝑙𝑒𝑛)−1≡𝑏(𝑎𝑖∗𝑙𝑒𝑛)−1(𝑚𝑜𝑑𝑚)𝑎𝑗≡𝑏(𝑎𝑖∗𝑙𝑒𝑛)−1(𝑚𝑜𝑑𝑚)4博弈论：4.1组合游戏一类组合游戏的定义：1、两位游戏者轮流操作2、游戏状态集有限，且不论怎么走都不会出现以前出现过的状态。3、谁不能操作谁输。4.2SG函数和SG定理对于一个上面这种游戏，设一个状态为𝑥，它的SG函数值定义为：𝑆𝐺(𝑥)=𝑚𝑒𝑥(𝑆)，其中S是𝑥的所有后继状态组成的集合，𝑚𝑒𝑥(𝑆)是不在集合中状态的SG值内的最小非负值。然后状态𝑥必败当且仅当它的SG函数值为0.SG定理：一个组合游戏的SG和是子游戏的SG的Nim和（异或和）。5数值运算：5.1Simpson启发式积分有时我们需要求一些图形的面积，当东西很不规则时，就不好做，这时，我们可以将所有东西都往下压，即计算每个𝑥对应的高度（所有东西的并在该位置的长度），然后问题转化为求一个曲线下面的面积，然后这不就是积分吗？然后计算机不是处理离散对象的吗？积分好像很难搞定。然后就有了这东西，设要算函数𝑓(𝑥)在区间[𝑥1,𝑥2]的值：S≈f(x1)+4f(x1+x22)+f(x1)6(x2−x1)当区间取得越短，面积就越精确。参考资料：NOI国家集训队论文《组合数学》《算法导论》《算法竞赛——入门经典训练指南》《新编实用算法分