This chapter introduces mathematical knowledge that may be useful in OI. Computer science is closely related to mathematics, and algorithm competitions in particular emphasize discrete, concrete mathematics represented by number theory, combinatorics, probability and expectation, and polynomials: it focuses on program implementation and real-world problems, and can appear in almost any category of problem.
In fact, the algorithms, data structures, and automata involved in algorithm competitions can also be considered part of mathematics. However, these topics are divided into specific chapters such as strings and presented with an application background to make them easier to understand. This chapter mainly introduces some basic concepts in mathematics, algebra, number theory, game theory, and probability theory. Applying this knowledge can help optimize other algorithms and data structures, for example:
- Use polynomials to optimize the convolution form of knapsack and solve some string problems.
- Many recursive problems have combinatorics or probability-and-expectation backgrounds. Generating functions can be used to derive and solve them further, and divide-and-conquer algorithms based on FFT can improve their efficiency.
- Use congruences and ring analysis to analyze the possible weight sums of non-simple paths in a graph modulo a given value, and maintain them with a weighted disjoint-set union structure.
In addition, high-school mathematics is the foundation of mathematics for informatics competitions. Learning the basic concepts and properties in textbooks well can better support the study of this chapter.