問題一覧 > 教育的問題

No.2267 群の公理

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 85
作問者 : 👑 p-adicp-adic / テスター : 箱星箱星
0 ProblemId : 8579 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-03-08 12:08:10

問題文

入力に 非負整数 $N$ と、$N$ 未満の非負整数に対して定義された $2$ 項演算 $\otimes$ が与えられます。

$\otimes$ が群演算であるか否かを判定してください。

　

以下、群について詳しくない人向けの説明を書きます。（クリックで開く）

　

まず $\otimes$ が結合的であるとは、次の条件を満たすということです：

  • （結合律）$N$ 未満の任意の非負整数 $n_0, n_1, n_2$ に対し、$(n_0 \otimes n_1) \otimes n_2 = n_0 \otimes (n_1 \otimes n_2)$ が成り立つ。

更に $\otimes$ が群演算であるとは、それが結合的でありかつ以下の $2$ 条件を満たすような $N$ 未満の非負整数 $e$ が存在するということです：

  • （単位律）$N$ 未満の任意の非負整数 $n$ に対し、$n \otimes e = n = e \otimes n$ が成り立つ。
  • （逆元律）$N$ 未満の任意の非負整数 $n$ に対し、$n \otimes i = e = i \otimes n$ を満たす $N$ 未満の非負整数 $i$ が存在する。

入力

入力は以下の形式で標準入力から $1 + N$ 行で与えられます：

  • $1$ 行目に $N$ が与えられます。
  • $N$ 未満の各非負整数 $n_0$ に対し、$2 + n_0$ 行目に $N$ 未満の各非負整数 $n_1$ に対する $n_0 \otimes n_1$ の値が、$n_1$ の小さい順に半角空白区切りで与えられます。

制約

入力は以下の制約を満たします：

  • $N$ は $0 \leq N \leq 30$ を満たす整数
  • $N$ 未満の任意の非負整数 $n_0, n_1$ に対し、$n_0 \otimes n_1$ は $0 \leq n_0 \otimes n_1 < N$ を満たす整数

出力

$\otimes$ が群演算である場合はYesと、群演算でない場合はNoと出力してください。

最後に改行してください。

サンプル

サンプル1
入力
1
0
出力
Yes

関係式

$\displaystyle 0 \otimes 0 = 0 $

で定まる $1$ 未満の非負整数に対する $2$ 項演算 $\otimes$ は群演算です。

群論を知っている人向けに言うと、これは $\mathbb{Z}$ の加法群の演算 $+$ を制限したものを部分群 $\{0\}$ に制限したものですね。

サンプル2
入力
2
0 1
1 0
出力
Yes

関係式

$\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} $

で定まる $2$ 未満の非負整数に対する $2$ 項演算 $\otimes$ は群演算です。

体論を知っている人向けに言うと、これは $2$ 元体 $\mathbb{Z}/2 \mathbb{Z}$ の加法群の群演算と同一視できますね。

サンプル3
入力
2
0 1
1 1
出力
No

関係式

$\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} $

で定まる $2$ 未満の非負整数に対する $2$ 項演算 $\otimes$ は群演算ではありません。

実際、$e = 0$ と定めると $1 \otimes i = e$ を満たす $2$ 未満の非負整数 $i$ が存在せず、$e = 1$ と定めると $0 \otimes e = 0$ を満たしません。

モノイドを知っている人向けに言うと、これは $\mathbb{N}$ のモノイド演算 $\max$ を部分モノイド $\{0,1\}$ に制限したものですね。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。