No.2397 Powers of ω
タグ : / 解いたユーザー数 5
作問者 : 👑
testestest
googol_S0
Problem Statement
This problem is based on ordinal arithmetic. Stating the usual definition of ordinal arithmetic would require explaining the complicated definition of ordinals, so here we instead introduce a set operation that extends ordinal arithmetic, using only the language of general sets.
For sets $X, Y$ and a non-negative integer $n$, we define the set $X + \omega^Y \times n$ recursively as follows:
$\displaystyle X + \omega^Y \times n = \left\{ \begin{array}{ll} X & (n = 0) \\ X \cup \{X\} & (n = 1 \land Y = \{\}) \\ \bigcup_{y \in Y} \bigcup_{m = 0}^{\infty} (X + \omega^y \times m) & (n = 1 \land Y \neq \{\}) \\ (X + \omega^Y \times (n-1)) + \omega^Y \times 1 & (n > 1) \end{array} \right. $
Note that in modern set theory, sets are formalized so that all of their elements are sets. Therefore each element $y$ of $Y$ is also a set, and $X + \omega^y \times m$ in the above formula is well-formed.
With respect to the operation defined in this way, $\{\} + \omega^{\{\{\}\}} \times 1$ is written as $\omega$ in the context of ordinals, and for ordinals $\alpha, \beta$ and a positive integer $n$, $\alpha + \omega^{\beta} \times n$ under this formulation coincides exactly with that under the usual ordinal arithmetic. It is known that every ordinal can be expressed as a finite sum of $0$ or more powers of $\omega$ with respect to the usual ordinal arithmetic. In particular, it is known that using the representation called the Cantor normal form with base $\omega$, the $\in$ relation between ordinals can be determined by lexicographic order. Note, however, that the definition of the lexicographic order on Cantor normal forms itself uses the $\in$ relation (of the ordinals appearing in the exponents).
For a positive integer $n$, let $(n_0,n_1)$ denote the unique pair of non-negative integers $(a,b)$ satisfying $n = (2a+1)2^b$.
For a non-negative integer $n$, we define the set $f(n)$ by the following recurrence:
$\displaystyle f(n) = \left\{ \begin{array}{ll} \displaystyle \{\} &\displaystyle (n = 0) \\ \displaystyle f(n_0) + \omega^{f(n_1)} \times 1 &\displaystyle (n \neq 0) \end{array} \right. $
Calculation examples: (click to expand)
For example, $f(0),f(1),f(3)$ can be computed as
$\displaystyle \begin{array}{rcl} \displaystyle f(0) &\displaystyle = &\displaystyle \{\} \\ \displaystyle f(1) &\displaystyle = &\displaystyle f((2 \times 0 + 1)2^0) = f(0) + \omega^{f(0)} \times 1 = \{\} + \omega^{\{\}} \times 1 = \{\} \cup \{\{\}\} = \{\{\}\} \\ \displaystyle f(3) &\displaystyle = &\displaystyle f((2 \times 1 + 1)2^0) = f(1) + \omega^{f(0)} \times 1 = \{\{\}\} + \omega^{\{\}} \times 1 = \{\{\}\} \cup \{\{\{\}\}\} = \{\{\},\{\{\}\}\} \end{array} $
as shown above.
Non-negative integers $N$ and $M$ are given as input.
Determine whether $f(N) \in f(M)$ holds.
Input
The input is given from standard input in $2$ lines in the following format:
On line $1$, $N$ is given in base $2$ notation.
On line $2$, $M$ is given in base $2$ notation.
Constraints
The input satisfies the following constraints:
- $N$ is a non-negative integer less than $2^{10^5}$
- $M$ is a non-negative integer less than $2^{10^5}$
Output
Print Yes if $f(N) \in f(M)$ holds, and No otherwise.
Print a newline at the end.
Sample
Sample 1
Input
0 0
Output
No
We have $f(0) = \{\}$. $\{\} \in \{\}$ does not hold.
Sample 2
Input
0 1
Output
Yes
We have $f(0) = \{\}$ and $f(1) = \{\{\}\}$. $\{\} \in \{\{\}\}$ holds.
Sample 3
Input
1 11
Note that the input is given in base $2$ notation.
Output
Yes
We have $f(1) = \{\{\}\}$ and $f(3) = \{\{\},\{\{\}\}\}$. $\{\{\}\} \in \{\{\},\{\{\}\}\}$ holds.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。