No.2267 Group Axioms
p-adic
箱星Problem Statement
You are given as input a non-negative integer $N$ and a $2$-ary operation $\otimes$ defined on the non-negative integers less than $N$.
Determine whether $\otimes$ is a group operation.
Below is an explanation for those who are not familiar with groups. (Click to open)
First, $\otimes$ is said to be associative if it satisfies the following condition:
- (Associative law) For any non-negative integers $n_0, n_1, n_2$ less than $N$, $(n_0 \otimes n_1) \otimes n_2 = n_0 \otimes (n_1 \otimes n_2)$ holds.
Furthermore, $\otimes$ is said to be a group operation if it is associative and there exists a non-negative integer $e$ less than $N$ satisfying the following $2$ conditions:
- (Identity law) For any non-negative integer $n$ less than $N$, $n \otimes e = n = e \otimes n$ holds.
- (Inverse law) For any non-negative integer $n$ less than $N$, there exists a non-negative integer $i$ less than $N$ satisfying $n \otimes i = e = i \otimes n$.
Input
The input is given from standard input in $1 + N$ lines in the following format:
- Line $1$ contains $N$.
- For each non-negative integer $n_0$ less than $N$, line $2 + n_0$ contains the values of $n_0 \otimes n_1$ for each non-negative integer $n_1$ less than $N$, in increasing order of $n_1$, separated by half-width spaces.
Constraints
The input satisfies the following constraints:
- $N$ is an integer satisfying $0 \leq N \leq 30$
- For any non-negative integers $n_0, n_1$ less than $N$, $n_0 \otimes n_1$ is an integer satisfying $0 \leq n_0 \otimes n_1 < N$
Output
Print Yes if $\otimes$ is a group operation, and No if it is not.
Print a newline at the end.
Sample
Sample 1
Input
1 0
Output
Yes
The relation
$\displaystyle 0 \otimes 0 = 0 $
determines a $2$-ary operation $\otimes$ on the non-negative integers less than $1$, and it is a group operation.
For those who know group theory, this is the operation $+$ of the additive group of $\mathbb{Z}$, restricted, and then restricted to the subgroup $\{0\}$.
Sample 2
Input
2 0 1 1 0
Output
Yes
The relations
$\displaystyle \begin{array}{rcl} \displaystyle 0 \otimes 0 &\displaystyle = & 0 \\ \displaystyle 0 \otimes 1 &\displaystyle = & 1 \\ \displaystyle 1 \otimes 0 &\displaystyle = & 1 \\ \displaystyle 1 \otimes 1 &\displaystyle = & 0 \end{array} $
determine a $2$-ary operation $\otimes$ on the non-negative integers less than $2$, and it is a group operation.
For those who know field theory, this can be identified with the group operation of the additive group of the $2$-element field $\mathbb{Z}/2 \mathbb{Z}$.
Sample 3
Input
2 0 1 1 1
Output
No
The relations
$\displaystyle \begin{array}{rcl} \displaystyle 0 \otimes 0 &\displaystyle = & 0 \\ \displaystyle 0 \otimes 1 &\displaystyle = & 1 \\ \displaystyle 1 \otimes 0 &\displaystyle = & 1 \\ \displaystyle 1 \otimes 1 &\displaystyle = & 1 \end{array} $
determine a $2$-ary operation $\otimes$ on the non-negative integers less than $2$, and it is not a group operation.
Indeed, if we set $e = 0$, there is no non-negative integer $i$ less than $2$ satisfying $1 \otimes i = e$, and if we set $e = 1$, $0 \otimes e = 0$ is not satisfied.
For those who know monoids, this is the monoid operation $\max$ of $\mathbb{N}$ restricted to the submonoid $\{0,1\}$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。