Introduction to Mathematics

This chapter introduces mathematical knowledge that may be used in OI. Computer science is closely related to mathematics, and algorithm competitions particularly emphasize discrete and concrete mathematics represented by number theory, combinatorics, probability and expectation, and polynomials: they focus on program implementation and real-world problems, and can appear in almost any category of problems.

In fact, algorithms, data structures, automata, etc., involved in algorithm competitions can also be considered part of mathematics. However, these topics are subdivided into specific chapters such as strings, with application contexts for better understanding. 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:

Using polynomials to optimize convolution-form knapsack problems for solving certain string problems.
Many recurrence-type problems are based on combinatorics or probability and expectation, which can be further derived and solved using generating functions, and algorithm efficiency can be optimized using divide-and-conquer based on FFT.
Analyzing possible weighted sums of non-simple paths on graphs under modulo using congruences and ring theory, and maintaining them with weighted union-find.

Additionally, high school mathematics forms the foundation for informatics competition mathematics. Mastering the basic concepts and properties from textbooks can better aid in learning the content of this chapter.

本页面最近更新：，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用