下载文档原格式
高中信息学竞赛知识点总结信息学竞赛是一项十分具有挑战性的比赛，要求参赛者具备扎实的计算机科学知识和解决问题的能力。
下面将对高中信息学竞赛的知识点进行总结，希望能够帮助参赛者更好地备战比赛。
一、基本概念1. 数据结构：包括线性表、栈、队列、树、图等数据结构的基本概念和操作。
2. 算法：包括排序算法、查找算法、递归算法、贪心算法、动态规划等常见算法。
3. 编程语言：掌握至少一种编程语言，如C++、Java、Python等，并熟练掌握其语法和基本操作。
二、算法与数据结构1. 线性表：包括数组、链表等线性结构的定义和常用操作。
2. 栈和队列：包括栈和队列的定义、特点和常用操作。
3. 树：包括二叉树、平衡树、堆等树结构的定义和常用操作。
4. 图：包括有向图和无向图的定义、表示方法和常用算法，如最短路径算法、最小生成树算法等。
5. 排序算法：包括冒泡排序、选择排序、插入排序、快速排序、归并排序等常用排序算法的原理和实现。
6. 查找算法：包括顺序查找、二分查找、哈希查找等常用查找算法的原理和实现。
三、计算机基础知识1. 计算机网络：包括OSI模型、TCP/IP协议、HTTP协议等网络基础知识。
2. 操作系统：包括进程管理、文件系统、内存管理等操作系统基础知识。
3. 数据库：包括关系型数据库、非关系型数据库以及SQL语言的基本操作。
四、编程能力1. 程序设计：包括算法设计、模块化设计、结构化编程等程序设计的基础知识。
2. 调试与优化：包括程序调试、性能优化、错误处理等编程技巧。
五、解题方法1. 分析问题：包括理解问题要求、确定问题的输入和输出、分析问题的复杂度等。
2. 设计算法：包括选择合适的数据结构和算法、设计有效的解题方法等。
3. 实现代码：包括编写正确、清晰、高效的代码。
4. 测试与优化：包括进行测试用例的设计、调试代码、性能优化等。
六、实践能力1. 编程实践：包括完成编程练习、解决实际问题、参与开源项目等。
信息学奥赛全部内容知识信息学奥赛作为一项具有挑战性和创造性的竞赛，考察的是选手在计算机科学领域的综合能力。
参与者需要掌握广泛的知识，包括算法、数据结构、编程语言等等。
本文将详细介绍信息学奥赛的全部内容知识。
一、算法与数据结构算法与数据结构是信息学奥赛中最重要的考察内容之一。
算法是解决具体问题的步骤和方法，而数据结构是组织和存储数据的方式。
选手需要熟悉各种经典算法，如排序算法、查找算法、图算法等，同时掌握常见的数据结构，如数组、链表、栈、队列、树等。
在实际比赛中，能够选择合适的算法和数据结构对解决问题至关重要。
二、编程语言信息学奥赛的编程语言没有特定限制，但大多数选手使用的是C++或Java。
选手需要深入理解所使用的编程语言，包括语法、特性和库函数等。
熟练掌握编程语言可以提高代码编写效率，减少错误的产生。
在比赛中，选手需要根据题目要求，合理选择编程语言的特性和库函数，以实现高效的解题算法。
三、图论图论是信息学奥赛中常见的题目类型之一。
选手需要掌握图的基本概念和常用算法。
了解图的遍历、最短路径、最小生成树等基本算法，并能够根据图的特性解决相关问题。
此外，选手还需了解图的表示方式，包括邻接矩阵、邻接表等，以便更好地解决图论问题。
四、动态规划动态规划是一种优化技术，常在信息学奥赛中用于解决具有重叠子问题的问题。
选手需要理解动态规划的基本原理，并能够设计状态转移方程、确定初始条件、以及最优解的选择。
熟练掌握动态规划的思想，可以在比赛中提高解题效率。
五、计算几何计算几何是信息学奥赛的一项知识点。
选手需要了解平面几何和空间几何的基本概念和常用算法。
熟悉点、线、面等几何元素的性质，并能够根据题目要求，使用几何算法解决实际问题。
六、数论数论是研究整数性质和相互关系的学科。
在信息学奥赛中，数论常常用于解决与数字有关的问题。
选手需要掌握最大公约数、最小公倍数、质数判断、素数筛法等基本概念和算法。
在解题过程中，选手还需要注意数学证明的合法性和严谨性。
初中信息学竞赛中的数学知识逻辑代数• 主要掌握逻辑代数的逻辑运算，逻辑运算和主要掌握逻辑代数的逻辑运算， Pascal中的逻辑运算相似，只不过符号不同而已。
中的逻辑运算相似，中的逻辑运算相似只不过符号不同而已。
• 逻辑代数的运算符和逻辑代数的运算符和Pascal的运算符有如下对应的运算符有如下对应关系：关系：┓：not（非）（∨：OR（或）（∧：AND（与）（它们的运算顺序和Pascal中的规定是一致的。
中的规定是一致的。
它们的运算顺序和中的规定是一致的逻辑代数P True True False False P True False Q True False True False P∨Q ∨ True True True False ┓P False True P∧Q True False False False 逻辑代数运算练习题设A=TRUE，B=FALSE，C=TRUE，，，， D=FALSE，求以下逻辑运算的结果：，求以下逻辑运算的结果：A ∨ B ∧ C=( ) ) ┓C ∧ A=( A ∧B ∨ C ∧D=( )排列组合问题• 此处我们只讨论最简单的排列组合问题。
此处我们只讨论最简单的排列组合问题。
• 乘法原理：完成一件事可以分为n个步骤，每个乘法原理：完成一件事可以分为个步骤，个步骤步骤又可分为a1,a2,a3，…，an个不同的方法，个不同的方法，步骤又可分为，，个不同的方法则完成此事的总方法有a1×a2×a3×…×an种方则完成此事的总方法有a1×a2×a3×…×an种方法。
• 加法原理：如果完成一件任务有类方法，在第加法原理：如果完成一件任务有n类方法类方法，一类方法中有m1种不同方法种不同方法，一类方法中有种不同方法，在第二类方法中有 m2种不同方法……在第类方法中有在第n类方法中有种不同种不同方法在第类方法中有mn种不同方法，那么完成这件任务共有N=m1+m2+…+mn 方法，那么完成这件任务共有排列组合问题• 加法原理典型例题：加法原理典型例题：从甲地到乙地，可以乘火车，也可以乘汽车，从甲地到乙地，可以乘火车，也可以乘汽车，还可以乘轮船。
信息竞赛必备知识点总结信息竞赛是一种在特定主题领域内，以比赛形式展示知识和技能的竞赛活动。
信息竞赛要求选手具备扎实的知识基础和综合能力，以便在竞争激烈的环境中取得优异的成绩。
在信息竞赛中，选手需要掌握丰富的知识，并且要能够对知识进行深入的理解和灵活的运用。
下面就信息竞赛必备的知识点进行总结。
一、数学数学是信息竞赛中必备的基础学科之一，其知识点主要包括以下几个方面：1. 算术与代数：包括数的性质、整数、分数、比例、百分数、方程与不等式等内容。
2. 几何与三角：包括图形的性质、平面几何、立体几何、相似性、三角函数等内容。
3. 数学分析：包括函数、极限、导数、积分、微分方程等内容。
4. 概率统计：包括概率、随机变量、统计学、分布函数、抽样调查等内容。
5. 数论与离散数学：包括素数、模运算、离散结构、组合数学等内容。
二、物理物理是信息竞赛中另一个重要的学科，其知识点主要包括以下几个方面：1. 力学：包括牛顿运动定律、运动学、动力学、静力学等内容。
2. 热学：包括热力学过程、热传导、热容与比热、热力学定律等内容。
3. 光学：包括光的本质、光的反射与折射、光的波动性质、光的干涉与衍射等内容。
4. 电磁学：包括电荷与电场、电位、电流、磁场、电磁感应等内容。
5. 声学：包括声波的产生与传播、声音的特性、声级的测量等内容。
三、化学化学是信息竞赛中的另一门重要学科，其知识点主要包括以下几个方面：1. 物质结构与性质：包括原子结构、分子结构、元素周期表、化学键、碳化合物等内容。
2. 化学反应与平衡：包括化学方程式、氧化还原反应、化学平衡、化学动力学等内容。
3. 化学变化与能量：包括热化学、热力学第一定律、热力学第二定律、活化能等内容。
4. 物质的组成与结构：包括溶液的性质、固液气体的性质、电解质等内容。
5. 化学实验与化学分析：包括化学实验的原理和方法、化学分析的方法和技术等内容。
四、生物生物学是信息竞赛中的重要学科之一，其知识点主要包括以下几个方面：1. 生物的基本单位：包括细胞的结构、生物膜、细胞器、生物大分子等内容。
信息学竞赛中的数学知识与应用技巧信息学竞赛在培养学生的计算机科学素养和解决问题能力方面起到了关键作用。
然而，我们不能忽视数学在信息学竞赛中的重要性。
本文将探讨数学在信息学竞赛中的知识和应用技巧。
一、离散数学与图论离散数学作为数学的一个重要分支，在信息学竞赛中扮演着重要角色。
图论作为离散数学的一个重要分支，在解决问题时发挥着关键作用。
许多信息学竞赛的问题可以转化为图论问题，因此，掌握好图论的基本概念和算法是至关重要的。
1. 图的表示与遍历在解决图论问题时，首先需要了解图的表示方法。
常用的表示方法有邻接矩阵和邻接表。
使用邻接矩阵可以方便地查找两个节点之间的边的关系，而使用邻接表可以更有效地存储大规模图的信息。
在了解了图的表示方法后，我们需要学会如何遍历图。
常用的遍历算法有深度优先搜索（DFS）和广度优先搜索（BFS）。
这两种算法在解决图相关问题时经常用到，对于信息学竞赛非常有帮助。
2. 最短路径和最小生成树最短路径和最小生成树是信息学竞赛中常见的问题类型。
Dijkstra 算法和Floyd算法是解决最短路径问题的经典算法。
Prim算法和Kruskal算法是解决最小生成树问题的经典算法。
熟练掌握这些算法可以帮助我们更好地解决与图相关的问题。
二、概率与统计在信息学竞赛中，概率与统计也是一个重要的数学知识点。
学生需要掌握概率论和统计学的基本概念，以便解决与概率和统计相关的问题。
1. 概率计算与统计分析在解决与概率相关的问题时，我们需要掌握概率的基本计算方法，如加法原理、乘法原理和条件概率等。
此外，对于离散型和连续型随机变量的概率分布函数的掌握也是重要的。
在解决与统计相关的问题时，我们需要掌握统计学的基本概念和统计分析方法。
常见的统计分析方法包括均值、方差、标准差、相关系数和回归分析等。
2. 概率与统计在信息学竞赛中的应用概率与统计在信息学竞赛中的应用非常广泛。
例如，在解决数据压缩、遗传算法和机器学习等问题时，概率与统计的知识经常被用到。
信息学竞赛中的数论与组合数学在信息学竞赛中，数论与组合数学是非常重要且常见的领域。
数论主要研究与整数有关的性质和规律，而组合数学则研究的是选择、排列和组合等离散结构的数学方法。
本文将探讨数论与组合数学在信息学竞赛中的应用，并介绍一些相关的知识和技巧。
一、数字的性质与规律1. 整数的除法规则在进行竞赛中，我们经常需要判断一个数能否被另一个数整除。
这时，我们需要了解整数的除法规则，包括最大公约数、最小公倍数等概念。
最大公约数可以通过欧几里得算法来求解，而最小公倍数可以通过两个数的乘积除以它们的最大公约数得到。
2. 同余与模运算同余是数论中一个重要的概念，它描述了两个数除以同一个数所得的余数相等。
在信息学竞赛中，我们经常会用到同余定理以及同余方程的解法。
二、排列与组合1. 排列的概念与应用排列是指从若干个元素中取出一部分进行有序排列的过程。
在信息学竞赛中，常常会碰到排列问题，比如计算不重复排列的个数、求解全排列等。
2. 组合与二项式定理组合是指从若干个元素中取出一部分进行无序选择的过程。
组合数学的一个重要定理是二项式定理，它描述了两个数的幂的展开式中各项的系数。
二项式定理在组合数学中有广泛的应用，可以用来计算组合数、求解多项式的展开等问题。
三、计数原理与概率1. 加法与乘法原理加法与乘法原理是组合数学中的基本原理，它们分别描述了求解多种情况下的计数问题的方法。
在信息学竞赛中，我们常常需要利用加法与乘法原理来计算满足某些条件的方案数。
2. 概率与期望值概率与期望值是随机事件的重要概念，在信息学竞赛中也有着广泛应用。
了解概率与期望值的计算方法能够帮助我们解决与随机事件相关的问题。
四、经典问题与技巧1. 质数与素数判定质数与素数是数论中一个重要的概念。
了解质数与素数的性质和判定方法，可以解决一些与质数相关的问题，比如求解素数的个数、质因数分解等。
2. 快速幂算法快速幂算法是一种高效计算幂的方法。
在信息学竞赛中，我们经常需要求解大数的幂，使用快速幂算法可以在较短的时间内得到结果。
信息学竞赛中的数学知识与应用随着科技的迅速发展，信息学竞赛成为了一项备受关注的知识竞赛。
信息学竞赛不仅考察学生在程序设计、算法等方面的能力，也对数学知识的掌握和应用提出了较高要求。
本文将从数学知识的重要性、数学在信息学竞赛中的应用以及数学的相关准备等方面展开论述。
一、数学知识在信息学竞赛中的重要性信息学竞赛作为一项具有较高难度的比赛，对参赛者的数学基础要求较为严格。
在信息学竞赛中，数学知识可以作为竞赛的基础，起到提升解题能力的作用。
首先，数学基础是理解和掌握计算机科学的基础。
信息学竞赛中，很多问题都需要通过数学的推理和计算来解决。
比如在算法设计和复杂度分析中，掌握好数学原理可以帮助选手更好地理解问题的本质和规律，从而设计出更高效的算法。
其次，数学作为一门逻辑性较强的科学，培养了参赛者的分析和解决问题的能力。
信息学竞赛中，很多题目需要选手进行数学建模和问题抽象，通过数学方法来解决实际问题。
数学训练使得选手能够培养出较强的逻辑思维和问题解决能力，在竞赛中应用数学知识更加得心应手。
另外，信息学竞赛的评判标准中，对于题目的正确性和效率都有较高要求。
数学的推理和计算能力是提高解题效率的关键因素。
例如，在解决图论问题时，对于图的遍历和最短路径算法的理解都离不开数学的支持。
二、数学在信息学竞赛中的应用数学在信息学竞赛中广泛应用于多个领域，包括算法设计、数据结构、图论等。
下面以一些典型的应用进行说明：1. 算法设计：在信息学竞赛中，算法设计是关键的一环。
而对于算法的正确性和效率分析，都需要借助于数学的推理和计算。
例如，对于时间复杂度的分析，需要运用到离散数学中的递推关系和大O表示法。
2. 数据结构：数据结构是信息学竞赛中另一个重要的知识点。
而在数据结构的选择和设计中，数学知识也起着关键的作用。
例如，在树的表示和遍历中，树的数学性质可以帮助选手更好地理解和操作树结构。
3. 图论：图论作为信息学竞赛中经常涉及的领域，也需要借助于数学的知识进行解决。
信息学竞赛中的数学知识应用信息学竞赛作为一项重要的学科竞赛，旨在培养学生的计算机应用能力和创新思维。
作为一门涵盖多学科知识的竞赛科目，信息学竞赛中的数学知识应用具有重要意义。
本文将探讨信息学竞赛中数学知识的应用，并说明其在算法设计、数据结构和复杂度分析等方面的重要性。
一、算法设计与数学知识的应用在信息学竞赛中，算法设计是解题的核心。
而数学知识在算法设计中发挥着重要的作用。
首先，数论是算法设计中常用的数学分支之一。
例如，在质因数分解、最大公约数和最小公倍数等问题中，数论的知识可以帮助选手更好地理解问题，并设计出高效的解决方法。
其次，概率与统计的应用也十分重要。
在随机算法、近似算法等问题中，概率与统计的知识可以帮助选手分析算法的正确性和复杂度，提高算法的效果。
二、数据结构与数学知识的应用数据结构是信息学竞赛中另一个重要的知识点。
数学知识在数据结构中的应用主要体现在图论和树结构上。
首先，图论是数学中的一个分支，它在信息学竞赛中的应用非常广泛。
例如，最短路径、最小生成树和网络流等问题都与图论相关，选手需要掌握图的遍历和图的特性，才能设计出高效的算法。
其次，树结构也是数据结构中的重点内容。
选手需要对树的遍历、树形动态规划等问题有深入的理解，并能够将数学模型转化成树的形式，从而解决实际问题。
三、复杂度分析与数学知识的应用复杂度分析是算法设计的一个重要环节，通过对算法的时间复杂度和空间复杂度进行分析，可以评估算法的效率。
在复杂度分析中，数学知识的应用非常广泛。
首先，级数和递推关系在复杂度的计算中经常出现。
选手需要熟悉常用的级数求和公式，如等差数列、等比数列和调和级数等，以便快速计算算法的复杂度。
其次，对数函数在复杂度分析中也是常见的。
例如，二分查找算法的时间复杂度就与对数相关，选手需要掌握对数函数的性质和计算方法，才能正确分析算法的复杂度。
综上所述，数学知识在信息学竞赛中的应用非常重要。
不仅可以帮助选手解决具体的问题，还可以培养选手的数学思维和分析能力。
信息学奥赛考察的数学知识
⼀级标准
⽆
⼆级标准
素数与合数，最⼤公约数，最⼩公倍数，互质数。
三级标准
逻辑运算，整数的质因数分解，随机函数。
筛选法，欧⼏⾥德算法
四级标准
集合及集合的运算，加法原理与乘法原理，简单的排列和组合。
五级标准
圆排列，可重集排列，鸽笼原理，素因数分解，幂函数，指数函数，对数函数，三⾓函数，模运算，不等式基础知识。
六级标准
可重集组合，⼆项式定理，数列与级数，归纳与递推，容斥原理，函数的连续性、函数的单调性和极值
七级标准
中国剩余定理，剩余类，概率基础知识，解析⼏何基础知识。
⼋级标准
矩阵概念及其基本运算，线性⽅程组的解法，迭代法，费马⼩定理和欧拉定理，母函数。
九级标准
计算⼏何基础知识（点积、叉积、凸包、半平⾯等知识及应⽤），数学期望。
⼗级标准
三维计算⼏何，组合游戏中的NIM问题和SG函数，群的概念，置换群，Burnside引理，Polya原理，莫⽐乌斯反演定理，FFT
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>。
信息学奥赛提高组必学知识点
在信息学奥赛提高组中，学生们需要掌握一些必学的知识点，以便在比赛中取得好成绩。
以下是一些重要的知识点：
1. 数据结构与算法：学生们应熟悉常用的数据结构，如数组、链表、栈、队列和树，并掌握它们的基本操作。
此外，了解常见的排序算法和搜索算法也是必不可少的，包括冒泡排序、快速排序、二分查找等。
2. 算法设计与分析：学生们需要学习如何设计高效的算法，并能够进行算法的正确性证明与复杂度分析。
掌握贪心算法、动态规划和回溯算法等常见的算法设计思想，对于解决复杂问题是非常有帮助的。
3. 图论与网络流：图论是信息学竞赛中常用的一种工具。
学生们需要了解图的表示方法，熟悉常见的图算法，如最短路径算法和最小生成树算法。
网络流算法是解决最大流最小割问题的经典方法，学生们应该掌握相关的算法和应用。
4. 动态规划：动态规划是一种常用的解决最优化问题的方法。
学生们需要学习动态规划的基本思想和常见的应用场景，并能够根据问题的特点设计出相应的动态规划算法。
5. 字符串处理：字符串处理在信息学竞赛中也是常见的问题类型。
学生们需要了解字符串的基本操作，如匹配、替换和分割等。
此外，掌握常见的字符串算法，如KMP算法和Trie树，对于解决字符串相关问题有很大帮助。
除了以上的知识点，学生们还应保持良好的编程习惯和解题思路，多做练习题和参加模拟比赛，提高自己的编程能力和解题思维。
老师和教练的指导也是非常重要的，他们可以帮助学生们找到适合自己的学习方法和解题技巧，提高竞赛成绩。
希望同学们能够认真学习这些知识点，为自己在信息学奥赛提高组中获得好成绩打下坚实的基础。
信息学竞赛中的数学知识简要梳理信息学竞赛经常涉及一些数学知识。
现在梳理一下。
目录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 个不同元素，其所有排列个个数：全排列P n =n!n 个不同元素，选出m 个来做全排列，排列数：P n m =n (n −1)(n −2)…(n −m +1) n 个不同元素，选出m 个的组合数：C n m=n!m!(n −m )!n 个元素，有m 种，第i 种有n i 个，每种则所有元素的排列数：P =C n n 1C n−n 1n 1C n−n 1−n 2n 1…C n m n m=n!n 1!n 2!n 3!n 4!…n m ! n 种元素，每种有无限多个，选出r 个（可重复）的方案数（用夹棍法理解）：N =C n+r−1n−1n 个不同元素，选出m 个，且每个都不相邻：N =C n−m+1m1.2 母函数母函数是一个函数，该函数有无限多项，且具有下面的形式：G (x )=a 0+a 1x +a 2x 2+⋯+a i x i +⋯=∏a i x i ∞i=0这样，一个母函数的的各项的系数就可以组成一个数列，并且任意一个数列都和母函数一一对应，对数列的研究就可以用母函数来帮忙了（还需要牛顿二项式定理来推导某些特殊级数的有限多项式表示）。
1.3 二项式定理 1.4 容斥原理：|⋃A i |=∑|A i |−∑|A i ∩A j |+∑|A i ∩A j ∩A k |…思想是：“统计所有的，减去多统计的，加上多减的，再减去多加的…”。
由德摩根定理：⋃A i ̅̅̅̅̅̅̅̅=⋂Ai ̅ 所以：N =|⋃A i |+|⋃A i ̅̅̅̅̅̅̅̅|=|⋃A i |+|⋂Ai ̅| |⋂Ai ̅|=N −|⋃A i | 这样，我们不光可以用容斥定理来统计“满足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)|G|N=∑∑[ s=a(s)]a∈As∈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扩展欧几里得求出ax+by=gcd (a,b)中的x,y和gcd (a,b)。
3.2逆元求a在模m下的逆元。
如果gcd(a,m)=1，则存在逆元，解方程：ax+my=gcd (a,m)得到的x就是a在模m下的逆元。
3.3解模意义下方程形式一：ax≡b ( mod m )对于形式一，将方程化简成:ax−my=b设d=gcd(a,m)，如果d|b，则方程有解，否则无解。
如果有解，即d|b，可以证明：ax≡b ( mod m )和a d x≡bd( modmd)同解（先把模方程化简成二元等式，然后可以发现前面方程的解也是后面方程的解，后面方程的解也是前面的解）。
然后解出这个方程（因为a/d和m/d互质，a/d∗x=1(mod m/d)必定存在解，将解乘以b/ d就是该方程的解）。
设初始解为x0，然后原始方程的d个解就是：x i=x0+i md,i∈[0,d−1]形式二：x≡b i ( mod m i )如果这个方程组的所有m互质，那么就是典型的中国剩余定理，如果不互质，就采用方程合并的思想（通法）。
将两个方程合并：x≡b1 ( mod m1 )x≡b2 ( mod m2 )先将方程变形为：x≡b1+m1yx≡b2+m2z然后联立起来，解出y，然后x=b1+m1y，然后上面的方程就等价于下面一个方程：x≡b12( mod m12) ,b12=b1+m1y, m12=lcm(m1,m2)一直这样合并，直到化简成只有一个方程，然后就完了。
3.4 莫比乌斯反演先说积性函数，如果一个函数f(x)满足，当x 和y 是质数时，f (xy )=f (x )f(y)则称f(x)是积性函数，如果没有质数限制，上式依然成立，则称f(x)为完全积性函数。
若一个函数f(x)是积性函数，那么可以定义其和函数g(x):g (x )=∑f(x)d|x可以证明（但我不知道），g(x)也是积性函数。
再来看两个特殊的函数，μ(x )和φ(x)，即Mobius 函数和Euler 函数，其中μ(x )={0 如果x 存在平方约数，否则(−1)rr =x 的质因数个数φ(x)=∑[gcd (i,x )==1]1≤i≤x可以证明这两个函数都是积性函数。
下面是它们的和函数：f (x )=[x =1]= ∑μ(x )d|xf (x )=x =∑φ(x)d|xMobius 反演就是根据和函数来求原函数，设f(x)的和函数是g(x)，那么：f (x )=∑μ(d )g(xd)d|x这一堆东西有什么用呢？转换！如果我们在一堆求和式中出现了[x ==1]或者x ，那么我们可以直接将他们看成和函数，用Mobius 函数或Euler 函数来表示，有时就可以达到化简的目的。
3.5 Miller-Rabin 素数测试对于一个数x ，如何判断它是否是质数？试除法要O(√x)的时间复杂度，如果给我们一个64位无符号数，让我们判断，那么这个方法就不行了。
Miller-Rabin 算法是一种随机算法，但只要随机次数一大，正确概率就很大很大了。
算法要用到两个定理： 定理一（费马小定理）：如果p 是质数，那么对于任何正整数a 有：a p−1≡1 ( mod p ) 定理二：如果p 是一个奇素数，那么x 2≡1 ( mod p )的解是±1。
我们需要利用这两个定理的逆否命题，即“如果不这样，就不是素数”。
所以如果算法返回否，那么该数一定不是素数，如果返回是，则有可能是素数。
算法流程：1、 设判定的数为x ，特判一下，若x 是大于2的奇数则继续。
2、 分解指数x −1=u2t ，其中t 尽量大。
3、 随机取一个正整数a 作为底数。
4、 依次计算底数为a ，指数为u,2u,2∗2u,2∗2∗2u …，的幂在模x 下的的值，将这列数看成一个数列，最后一项就是x 。
从第二项开始，如果某一项的值是1，判断它前面那一项的值是不是模意义下的1或-1，如果不是，根据定理二，返回否。
5、看最后一项是不是1，如果不是，根据定理一，返回否。
执行8~10次基本就可以保证正确性了。
3.6Pollard-Rho 因子分解这里只说一下大概步骤（思想？），加入要分解n，我们维护两个序列：x1,x2,x3,x4,x5,x6,…y1,y2,y3,y4,y5,…其中x i=f(x i−1) (x1=random(0,n−1))y i=x2i−1从头开始计算第一个序列，每计算完成一项，看gcd (x−y,n)（其中x和y是最新算出来的项）是否是n的非平凡因子，当x==y时退出,它的复杂度和正确性分析请看《算法导论》。
3.7BSGS 离散对数问题：给定正整数a,b,m，求满足a x≡b ( mod m )的x。
我们知道aφ(m)≡1 ( mod m )，意思是a0,a1,a2,a3,…有一个长度为φ(m)的循环，我们可以只枚举长度为φ(m)的一段就可以知道解或者无解。
但是枚举依旧吃不消，那么我们可以分块算，简单来说，就是先算长度为φ(m)的那个序列个前len项，将它们放到一个hash表中，然后每次计算a i∗len的值，计算它的逆，再计算逆与b的乘积，看hash表中有没有算出来的这个值，如果有，就找到了，找完都没有那就真的没有了。
原理就是：a x≡a i∗len+j≡b ( mod m )a i∗len+j(a i∗len)−1≡b(a i∗len)−1( mod m )a j≡b(a i∗len)−1 ( mod m )4博弈论：4.1组合游戏一类组合游戏的定义：1、两位游戏者轮流操作2、游戏状态集有限，且不论怎么走都不会出现以前出现过的状态。
3、谁不能操作谁输。
4.2SG函数和SG定理对于一个上面这种游戏，设一个状态为x，它的SG函数值定义为：SG(x)=mex(S)，其中S是x的所有后继状态组成的集合，mex(S)是不在集合中状态的SG值内的最小非负值。
