*Acknowledgements: ChatGPT for Grammar fixing.*↵
↵
In mathematics, ordinals extend the concept of counting beyond finite numbers and incorporate infinite sequences. From a graph theory perspective, you can think of ordinals as a hierarchy of "layers" or "levels" that represent different sizes and types of infinity.↵
↵
## Basic Concepts↵
↵
In this blog, we define ordinals as competitive graphs $\Gamma$, where a competitive graph is a directed graph in which exactly one of $(u, v)$ or $(v, u)$ is included in the edge set for every pair of distinct vertices $u$ and $v$. These graphs are characterized by the absence of loops and reversed rays, where a reversed ray refers to a sequence of vertices $v_0, v_1, v_2, \dots$ with edges $(v_1, v_0), (v_2, v_1), (v_3, v_2), \dots$.↵
↵
Finite ordinals correspond to natural numbers. For instance, $0$ represents the empty graph, and $1$ denotes the graph with a single vertex. An example is provided below:↵
↵
↵
↵
In fact, the set of natural numbers $\mathbb{Z}_{\ge 0}$, often denoted as $\omega$, can be interpreted as an ordinal: $\Gamma_\omega = (V, E)$, where $V = \mathbb{Z}_{\ge 0}$ and $E = \\{(i, j) : i < j\\}$. However, $\mathbb{Z}$ cannot be considered an ordinal in a similar manner, due to the presence of a reversed ray, as exemplified by the sequence of vertices $v_i = -i$.↵
↵
We define $\alpha \le \beta$ if $\beta$ can be viewed as a subgraph of $\alpha$. Similarly, $\alpha = \beta$ if and only if $\alpha \le \beta$ and $\beta \le \alpha$. As is familiar, the relationship between ordinals is either $\alpha < \beta$, $\alpha = \beta$, or $\alpha > \beta$.↵
↵
<spoiler summary="Proof (Maybe Mathy)">↵
Every ordinal has an initial element, which is a vertex without incoming edges. If this were not the case, then for every vertex $v$, there would exist an incoming edge $v' \to v$, creating a reversed ray: $\dots \to v' ' \to v' \to v$. It can be easily proven that the initial element $v_0$ is unique.↵
↵
We define a set $S_v$ for every vertex $v$ of $\alpha$ as follows: $S_{v_0} = \varnothing$, and for any vertex $v \ne v_0$, $S_v = \\{ S_u : (u, v) \in E \\}$. If there exists a $S_x$ that is undefined, then: (1) $x$ cannot be an initial element, so there must be an incoming edge $x' \to x$; (2) Similarly, $x'$ cannot be an initial element, so there must be an incoming edge $x' ' \to x'$. By continuing this logic chain, we can demonstrate that $\dots \to x' ' \to x' \to x$ forms a reversed ray. Therefore, every $S_x$ is defined.↵
↵
It can be observed that $\alpha \le \beta$ if and only if $S_\alpha \le S_\beta$, and $\alpha < \beta$ if and only if $S_\alpha \in S_\beta$. Let $S_\alpha = \\{ S_v : v \in \alpha \\}$ (mathematicians often define ordinals as such a set rather than as a graph). Suppose $S = S_\alpha \cap S_\beta$. If $S \ne S_\alpha$ and $S \ne S_\beta$, then $S$ is an element of both $S_\alpha$ and $S_\beta$, so $S \in S_\alpha \cap S_\beta = S$. By the Axiom of Regularity, no set $S$ can satisfy $S \in S$. Therefore, $S = S_\alpha$ or $S = S_\beta$, which implies that $S_\alpha \subseteq S_\beta$ or $S_\beta \subseteq S_\alpha$.↵
</spoiler>↵
↵
In fact, for every set $A$ of ordinals, there exists an ordinal $\min A$ in the set $A$. The proof is straightforward: one can obtain $\min A$ by taking the union of all the $S_\alpha$, where $\alpha \in A$ and $S$ is the set defined previously.↵
↵
The successor of an ordinal $\alpha$ is a new graph $G$ where the vertices include all the vertices of $\alpha$ along with an additional vertex $v$. All edges $(w, v)$, where $w$ is a vertex in $\alpha$, are added. The successor of $\alpha$ is denoted as $\alpha^+$. It is evident that $\alpha < \alpha^+$. Consequently, we can define the $n$-th successor of $\alpha$, denoted as $\alpha + n$.↵
↵
To understand how addition and multiplication of ordinals work, consider the following definitions: For ordinals $\alpha$ and $\beta$, $\alpha + \beta$ is the ordinal with vertices formed by the disjoint union $\alpha \sqcup \beta$ (where $\sqcup$ denotes the disjoint union of sets) and edges of three types: the edges from $\alpha$ itself, the edges from $\beta$ itself, and new edges $(u, v)$ where $u$ is a vertex of $\alpha$ and $v$ is a vertex of $\beta$. Similarly, $\alpha \times \beta$ is the ordinal with vertices formed by pairs $(u, v)$, and edges formed by pairs $((u, v), (u', v'))$, where either $(u, u') \in E_\alpha$ or $u = u'$ and $(v, v') \in E_\beta$.↵
↵
It is important to note that commutativity does not hold for ordinals: $1 + \omega = \omega \ne \omega + 1$, and $2 \omega = \omega \ne \omega 2$. However, associativity does hold.↵
↵
Here are some properties of ordinals:↵
↵
* If $\beta < \gamma$, then $\alpha + \beta < \alpha + \gamma$.↵
* If $\alpha < \beta$, there exists a unique $\gamma$ such that $\alpha + \gamma = \beta$.↵
* For ordinals $\gamma$ and $\alpha$, there exists a unique pair of ordinals $\beta$ and $\delta$ such that $\gamma = \alpha \beta + \delta$.↵
* For $\gamma > 0$, there exists a unique Cantor normal form $\gamma = \omega^{\alpha_1} k_1 + \dots + \omega^{\alpha_n} k_n$, where $n \ge 1$, $\alpha_1 > \alpha_2 > \dots > \alpha_n$ are ordinals, and $k_1, k_2, \dots, k_n \in \mathbb{Z}_{> 0}$.↵
↵
## Application in CP/OI↵
To be updated. An example problem will be [problem:1149E]Consider a directed graph $\Gamma$ and the SG (Sprague-Grundy) function $f$ defined on it. If $\Gamma$ is finite, $f$ can be easily represented as a natural number-valued function. However, when we extend the SG function to handle infinite graphs, we need to incorporate ordinals.↵
↵
For instance, in problem [problem:1149E], we observe that a state can have infinitely many successors. To illustrate this, consider the special case where the graph is $1 \to 2$.↵
↵
- If $h_1 = 0$, then the SG function is $h_2$, which can be directly verified.↵
- If $h_1 = 1$ and $h_2 = 0$, the successors are every state $0 \to n$, where $n$ is a natural number. Consequently, the SG function for the state $h_1 = 1$ and $h_2 = 0$ is $\omega$, as $\omega$ is the smallest ordinal not included in $\mathbb{N}$.↵
↵
Continuing this pattern, for general values $h_1$ and $h_2$, we find that the SG function is given by $\omega h_1 + h_2$.↵
↵
More generally, for any directed graph $\Gamma$ considered as a normal directed graph game, the SG function $\sigma$ can be expressed in terms of ordinals. Specifically, the SG function can be written as ↵
↵
$$↵
\omega^n a_n + \omega^{n-1} a_{n-1} + \dots + a_0,↵
$$ ↵
↵
where the coefficients $a_k$ are given by↵
↵
$$↵
a_k = \sum_{\sigma(x) = k} h_x.↵
$$↵
↵
By fundamental principles in game theory, a game is a P-position (a position from which the second player has a winning strategy) if and only if its SG function is non-zero. This completes the discussion of the problem.↵
↵
An another example is [最长待机 / Longest Standby](https://www.luogu.com.cn/problem/P10222).↵
↵
<spoiler summary="Translated Statement">↵
You have a program composed of $n$ functions, where the $i$-th function has a type $e_i$ and a sequence of sub-function indices $Q_i = (Q_{i,1}, Q_{i,2}, \ldots, Q_{i,l_i})$. The sequence $Q_i$ can be empty, in which case $l_i = 0$.↵
↵
The following conditions must hold for the functions:↵
- $n \ge 1$.↵
- For all $1 \le i \le n$, $e_i \in \\{0, 1\\}$.↵
- For all $1 \le i \le n$, elements in $Q_i$ are unique and must be integers from the range $[i + 1, n]$.↵
- For all $2 \le j \le n$, there exists exactly one $Q_i (1 \le i \le n)$ that contains $j$.↵
↵
### Function Call Mechanics↵
↵
When calling function $i (1 \le i \le n)$, the following occurs:↵
1. If $e_i = 0$, set variable $r_i$ to $1$. Otherwise, a positive integer value must be input for $r_i$.↵
2. If $Q_i$ is empty, the program waits for $r_i$ seconds. Otherwise, it repeats the following for $r_i$ times:↵
— Call the functions with indices $Q_{i,1}, Q_{i,2}, \ldots, Q_{i,l_i}$.↵
↵
If a function of type $1$ is called multiple times, each call requires a separate input for $r_j$.↵
↵
The only action consuming time is "waiting $r$ seconds"; all other operations (calling functions and inputting values) occur instantaneously.↵
↵
### Game Rules↵
↵
Two players prepare their functions and choose one to call. They know each other's function structure and selected function.↵
↵
At time $0$, both players concurrently call their selected functions. The two players can observe all input values from time $0$ to $t-1$ and adjust their inputs accordingly at time $t$, but they cannot know each other's inputs at time $t$.↵
↵
The player whose function call finishes first loses; if both finish simultaneously, it results in a draw.↵
↵
Both players are assumed to be perfectly intelligent. If one player can guarantee a win, the game is deemed unfair. If both cannot guarantee a win, the game is fair.↵
↵
### Operations↵
↵
You can perform two types of operations on the program:↵
↵
1. Given $k$, toggle $e_k$ (i.e., set $e_k$ to $1 - e_k$).↵
2. Given $k$, play a game where one player calls their function $k$.↵
↵
### Constraints↵
↵
$1 \le n \le 5 \times 10^5$ and $1 \le q \le 2 \times 10^5$, where $q$ is the number of operations. (You can try to solve it in $\mathrm O(nq)$ time first and optimize it.)↵
</spoiler>↵
↵
Try to solve it yourself! :) After solving it you can understand why $1 + \omega \ne \omega + 1$.
↵
In mathematics, ordinals extend the concept of counting beyond finite numbers and incorporate infinite sequences. From a graph theory perspective, you can think of ordinals as a hierarchy of "layers" or "levels" that represent different sizes and types of infinity.↵
↵
## Basic Concepts↵
↵
In this blog, we define ordinals as competitive graphs $\Gamma$, where a competitive graph is a directed graph in which exactly one of $(u, v)$ or $(v, u)$ is included in the edge set for every pair of distinct vertices $u$ and $v$. These graphs are characterized by the absence of loops and reversed rays, where a reversed ray refers to a sequence of vertices $v_0, v_1, v_2, \dots$ with edges $(v_1, v_0), (v_2, v_1), (v_3, v_2), \dots$.↵
↵
Finite ordinals correspond to natural numbers. For instance, $0$ represents the empty graph, and $1$ denotes the graph with a single vertex. An example is provided below:↵
↵
↵
↵
In fact, the set of natural numbers $\mathbb{Z}_{\ge 0}$, often denoted as $\omega$, can be interpreted as an ordinal: $\Gamma_\omega = (V, E)$, where $V = \mathbb{Z}_{\ge 0}$ and $E = \\{(i, j) : i < j\\}$. However, $\mathbb{Z}$ cannot be considered an ordinal in a similar manner, due to the presence of a reversed ray, as exemplified by the sequence of vertices $v_i = -i$.↵
↵
We define $\alpha \le \beta$ if $\beta$ can be viewed as a subgraph of $\alpha$. Similarly, $\alpha = \beta$ if and only if $\alpha \le \beta$ and $\beta \le \alpha$. As is familiar, the relationship between ordinals is either $\alpha < \beta$, $\alpha = \beta$, or $\alpha > \beta$.↵
↵
<spoiler summary="Proof (Maybe Mathy)">↵
Every ordinal has an initial element, which is a vertex without incoming edges. If this were not the case, then for every vertex $v$, there would exist an incoming edge $v' \to v$, creating a reversed ray: $\dots \to v' ' \to v' \to v$. It can be easily proven that the initial element $v_0$ is unique.↵
↵
We define a set $S_v$ for every vertex $v$ of $\alpha$ as follows: $S_{v_0} = \varnothing$, and for any vertex $v \ne v_0$, $S_v = \\{ S_u : (u, v) \in E \\}$. If there exists a $S_x$ that is undefined, then: (1) $x$ cannot be an initial element, so there must be an incoming edge $x' \to x$; (2) Similarly, $x'$ cannot be an initial element, so there must be an incoming edge $x' ' \to x'$. By continuing this logic chain, we can demonstrate that $\dots \to x' ' \to x' \to x$ forms a reversed ray. Therefore, every $S_x$ is defined.↵
↵
It can be observed that $\alpha \le \beta$ if and only if $S_\alpha \le S_\beta$, and $\alpha < \beta$ if and only if $S_\alpha \in S_\beta$. Let $S_\alpha = \\{ S_v : v \in \alpha \\}$ (mathematicians often define ordinals as such a set rather than as a graph). Suppose $S = S_\alpha \cap S_\beta$. If $S \ne S_\alpha$ and $S \ne S_\beta$, then $S$ is an element of both $S_\alpha$ and $S_\beta$, so $S \in S_\alpha \cap S_\beta = S$. By the Axiom of Regularity, no set $S$ can satisfy $S \in S$. Therefore, $S = S_\alpha$ or $S = S_\beta$, which implies that $S_\alpha \subseteq S_\beta$ or $S_\beta \subseteq S_\alpha$.↵
</spoiler>↵
↵
In fact, for every set $A$ of ordinals, there exists an ordinal $\min A$ in the set $A$. The proof is straightforward: one can obtain $\min A$ by taking the union of all the $S_\alpha$, where $\alpha \in A$ and $S$ is the set defined previously.↵
↵
The successor of an ordinal $\alpha$ is a new graph $G$ where the vertices include all the vertices of $\alpha$ along with an additional vertex $v$. All edges $(w, v)$, where $w$ is a vertex in $\alpha$, are added. The successor of $\alpha$ is denoted as $\alpha^+$. It is evident that $\alpha < \alpha^+$. Consequently, we can define the $n$-th successor of $\alpha$, denoted as $\alpha + n$.↵
↵
To understand how addition and multiplication of ordinals work, consider the following definitions: For ordinals $\alpha$ and $\beta$, $\alpha + \beta$ is the ordinal with vertices formed by the disjoint union $\alpha \sqcup \beta$ (where $\sqcup$ denotes the disjoint union of sets) and edges of three types: the edges from $\alpha$ itself, the edges from $\beta$ itself, and new edges $(u, v)$ where $u$ is a vertex of $\alpha$ and $v$ is a vertex of $\beta$. Similarly, $\alpha \times \beta$ is the ordinal with vertices formed by pairs $(u, v)$, and edges formed by pairs $((u, v), (u', v'))$, where either $(u, u') \in E_\alpha$ or $u = u'$ and $(v, v') \in E_\beta$.↵
↵
It is important to note that commutativity does not hold for ordinals: $1 + \omega = \omega \ne \omega + 1$, and $2 \omega = \omega \ne \omega 2$. However, associativity does hold.↵
↵
Here are some properties of ordinals:↵
↵
* If $\beta < \gamma$, then $\alpha + \beta < \alpha + \gamma$.↵
* If $\alpha < \beta$, there exists a unique $\gamma$ such that $\alpha + \gamma = \beta$.↵
* For ordinals $\gamma$ and $\alpha$, there exists a unique pair of ordinals $\beta$ and $\delta$ such that $\gamma = \alpha \beta + \delta$.↵
* For $\gamma > 0$, there exists a unique Cantor normal form $\gamma = \omega^{\alpha_1} k_1 + \dots + \omega^{\alpha_n} k_n$, where $n \ge 1$, $\alpha_1 > \alpha_2 > \dots > \alpha_n$ are ordinals, and $k_1, k_2, \dots, k_n \in \mathbb{Z}_{> 0}$.↵
↵
## Application in CP/OI↵
↵
For instance, in problem [problem:1149E], we observe that a state can have infinitely many successors. To illustrate this, consider the special case where the graph is $1 \to 2$.↵
↵
- If $h_1 = 0$, then the SG function is $h_2$, which can be directly verified.↵
- If $h_1 = 1$ and $h_2 = 0$, the successors are every state $0 \to n$, where $n$ is a natural number. Consequently, the SG function for the state $h_1 = 1$ and $h_2 = 0$ is $\omega$, as $\omega$ is the smallest ordinal not included in $\mathbb{N}$.↵
↵
Continuing this pattern, for general values $h_1$ and $h_2$, we find that the SG function is given by $\omega h_1 + h_2$.↵
↵
More generally, for any directed graph $\Gamma$ considered as a normal directed graph game, the SG function $\sigma$ can be expressed in terms of ordinals. Specifically, the SG function can be written as ↵
↵
$$↵
\omega^n a_n + \omega^{n-1} a_{n-1} + \dots + a_0,↵
$$ ↵
↵
where the coefficients $a_k$ are given by↵
↵
$$↵
a_k = \sum_{\sigma(x) = k} h_x.↵
$$↵
↵
By fundamental principles in game theory, a game is a P-position (a position from which the second player has a winning strategy) if and only if its SG function is non-zero. This completes the discussion of the problem.↵
↵
An another example is [最长待机 / Longest Standby](https://www.luogu.com.cn/problem/P10222).↵
↵
<spoiler summary="Translated Statement">↵
You have a program composed of $n$ functions, where the $i$-th function has a type $e_i$ and a sequence of sub-function indices $Q_i = (Q_{i,1}, Q_{i,2}, \ldots, Q_{i,l_i})$. The sequence $Q_i$ can be empty, in which case $l_i = 0$.↵
↵
The following conditions must hold for the functions:↵
- $n \ge 1$.↵
- For all $1 \le i \le n$, $e_i \in \\{0, 1\\}$.↵
- For all $1 \le i \le n$, elements in $Q_i$ are unique and must be integers from the range $[i + 1, n]$.↵
- For all $2 \le j \le n$, there exists exactly one $Q_i (1 \le i \le n)$ that contains $j$.↵
↵
### Function Call Mechanics↵
↵
When calling function $i (1 \le i \le n)$, the following occurs:↵
1. If $e_i = 0$, set variable $r_i$ to $1$. Otherwise, a positive integer value must be input for $r_i$.↵
2. If $Q_i$ is empty, the program waits for $r_i$ seconds. Otherwise, it repeats the following for $r_i$ times:↵
— Call the functions with indices $Q_{i,1}, Q_{i,2}, \ldots, Q_{i,l_i}$.↵
↵
If a function of type $1$ is called multiple times, each call requires a separate input for $r_j$.↵
↵
The only action consuming time is "waiting $r$ seconds"; all other operations (calling functions and inputting values) occur instantaneously.↵
↵
### Game Rules↵
↵
Two players prepare their functions and choose one to call. They know each other's function structure and selected function.↵
↵
At time $0$, both players concurrently call their selected functions. The two players can observe all input values from time $0$ to $t-1$ and adjust their inputs accordingly at time $t$, but they cannot know each other's inputs at time $t$.↵
↵
The player whose function call finishes first loses; if both finish simultaneously, it results in a draw.↵
↵
Both players are assumed to be perfectly intelligent. If one player can guarantee a win, the game is deemed unfair. If both cannot guarantee a win, the game is fair.↵
↵
### Operations↵
↵
You can perform two types of operations on the program:↵
↵
1. Given $k$, toggle $e_k$ (i.e., set $e_k$ to $1 - e_k$).↵
2. Given $k$, play a game where one player calls their function $k$.↵
↵
### Constraints↵
↵
$1 \le n \le 5 \times 10^5$ and $1 \le q \le 2 \times 10^5$, where $q$ is the number of operations. (You can try to solve it in $\mathrm O(nq)$ time first and optimize it.)↵
</spoiler>↵
↵
Try to solve it yourself! :) After solving it you can understand why $1 + \omega \ne \omega + 1$.
