信息学竞赛中的数学知识简要梳理
信息学竞赛经常涉及一些数学知识。现在梳理一下。
1组合数学：
1.1排列与组合
1.4容斥原理
1.5鸽巢原理
1.6论（特别是置换）
1.7Burnside引理与Polya定理
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个不同元素，选出m个来做全排列，排列数：
n个不同元素，选出m个的组合数：
n个元素，有m种，第i种有ni个，每种则所有元素的排列数：
n种元素，每种有无限多个，选出r个（可重复）的方案数（用夹棍法理解）：
n个不同元素，选出m个，且每个都不相邻：
1.2母函数
母函数是一个函数，该函数有无限多项，且具有下面的形式：
这样，一个母函数的的各项的系数就可以组成一个数列，并且任意一个数列都和母函数一一对应，对数列的研究就可以用母函数来帮忙了（还需要牛顿二项式定理来推导某些特殊级数的有限多项式表示）。
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上的等价关系：如果能通过置换中的置换变成，那么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下的逆元。如果，则存在逆元，解方程：
得到的x就是a在模m下的逆元。
3.3解模意义下方程
形式一：
对于形式一，将方程化简成:
设，如果，则方程有解，否则无解。
如果有解，即，可以证明：
和
美容牙科同解（先把模方程化简成二元等式，然后可以发现前面方程的解也是后面方程的解，后面方程的解也是前面的解）。
然后解出这个方程（）。设初始解为，然后原始方程的d个解就是：
库存物资
形式二：
如果这个方程组的所有m互质，那么就是典型的中国剩余定理，如果不互质，就采用方程合并的思想（通法）。将两个方程合并：
先将方程变形为：
然后联立起来，解出，然后，然后上面的方程就等价于下面一个方程：
一直这样合并，直到化简成只有一个方程，然后就完了。
3.4莫比乌斯反演
先说积性函数，如果一个函数满足，当和是质数时，
则称是积性函数，如果没有质数限制，上式依然成立，则称为完全积性函数。
若一个函数是积性函数，那么可以定义其和函数:
可以证明（但我不知道），也是积性函数。
再来看两个特殊的函数，和，即Mobius函数和Euler函数，其中
可以证明这两个函数都是积性函数。下面是它们的和函数：
Mobius反演就是根据和函数来求原函数，设的和函数是，那么：
这一堆东西有什么用呢？转换！如果我们在一堆求和式中出现了或者，那么我们可以直接将他们看成和函数，用Mobius函数或Euler函数来表示，有时就可以达到化简的目的。
3.5Miller-Rabin素数测试
对于一个数，如何判断它是否是质数？试除法要的时间复杂度，如果给我们一个64位无符号数，让我们判断，那么这个方法就不行了。
Miller-Rabin算法是一种随机算法，但只要随机次数一大，正确概率就很大很大了。
算法要用到两个定理：
定理一（费马小定理）：如果是质数，那么对于任何正整数有：
定理二：如果是一个奇素数，那么的解是。
我们需要利用这两个定理的逆否命题，即“如果不这样，就不是素数”。所以如果算法返回否，那么该数一定不是素数，如果返回是，则有可能是素数。
算法流程：
1、设判定的数为，特判一下，若是大于2的奇数则继续。
2、分解指数，其中尽量大。北京科瑞集团
3、随机取一个正整数作为底数。
4、依次计算底数为，的幂在模下的的值，将这列数看成一个数列，最后一项就是。从第二项开始，如果某一项的值是1，判断它前面那一项的值是不是模意义下的1或-1，如果不是，根据定理二，返回否。
5、看最后一项是不是1，如果不是，根据定理一，返回否。
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议