問題一覧 > 教育的問題

No.2446 Exact Sequence

レベル : / AI推定難易度 : 1300 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 17
作問者 : 👑 p-adic / テスター : 👑 AngrySadEight
お気に入りにしたユーザー ProblemId : 9631 / 自分の提出
問題文最終更新日: 2023-08-30 09:55:39
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 402 (順位表) の他の問題:

Problem Statement

You are given $3$ positive integers $L, M, N$, an $L \times M$ matrix $A$ with integer coefficients, and an $M \times N$ matrix $B$ with integer coefficients as input.

 

$(A,B)$ is called a good pair if, for every $M$-dimensional column vector $x$ with real coefficients, the following $2$ conditions are equivalent:

  1. $Ax$ is the zero vector.
  2. There exists an $N$-dimensional column vector $y$ with real coefficients satisfying $x = By$.

 

Determine whether $(A,B)$ is a good pair.

Background

Let $g$ denote the linear map $\mathbb{R}^M \to \mathbb{R}^L$ defined by left multiplication by $A$, and let $f$ denote the linear map $\mathbb{R}^N \to \mathbb{R}^M$ defined by left multiplication by $B$. In the field of homological algebra, the statement that $(A,B)$ is a good pair is expressed by saying that the sequence of linear maps

$\displaystyle \mathbb{R}^N \stackrel{f}{\to} \mathbb{R}^M \stackrel{g}{\to} \mathbb{R}^L $

is exact, or that it is an exact sequence. The concept of exact sequences is used extensively in the theory of modules in algebra, in geometry, and elsewhere, and is also widely treated in category theory; it is one of the fundamental tools of modern mathematics.

Input

Below, for a positive integer $i$ not exceeding the number of columns of a matrix $C$ and a positive integer $j$ not exceeding its number of rows, $C_{i,j}$ denotes the $(i,j)$ entry of $C$.

The input is given from standard input in $1 + L + M$ lines, in the following format.

  • Line $1$ contains $L, M, N$, separated by single-byte spaces.
  • For each positive integer $i$ not exceeding $L$, line $1 + i$ contains $A_{i,j}$ for each positive integer $j$ not exceeding $M$, in increasing order of $j$, separated by single-byte spaces.
  • For each positive integer $j$ not exceeding $M$, line $1 + L + j$ contains $B_{j,k}$ for each positive integer $k$ not exceeding $N$, in increasing order of $k$, separated by single-byte spaces.
$L$ $M$ $N$
$A_{1,1}$ $\cdots$ $A_{1,M}$
$\vdots$
$A_{L,1}$ $\cdots$ $A_{L,M}$
$B_{1,1}$ $\cdots$ $B_{1,N}$
$\vdots$
$B_{M,1}$ $\cdots$ $B_{M,N}$

Constraints

The input satisfies the following constraints:

  • $L, M , N$ are integers satisfying $1 \leq L, M, N$ and $LM, MN \leq 15$
  • Each entry $a$ of $A , B$ is an integer satisfying $-6 \leq a \leq 6$

Output

Print Yes if $(A,B)$ is a good pair, and No if it is not.

Print a newline at the end.

Sample

Sample 1
Input
1 1 1
-2
3
Output
No

We have $A = (-2)$ and $B = (3)$. If we define the $1$-dimensional column vector $x$ with real coefficients as $(1)$, then $Ax = (-2 \cdot 1) = (-2)$ is not the zero vector, but if we define the $L = 1$-dimensional column vector $y$ with real coefficients as $(3^{-1})$, then $x = By$ holds.

Sample 2
Input
1 1 1
0
0
Output
No

We have $A = (0)$ and $B = (0)$. If we define the $1$-dimensional column vector $x$ with real coefficients as $(1)$, then $Ax = (0 \cdot 1) = (0)$ is the zero vector, but there exists no $L = 1$-dimensional column vector $y$ with real coefficients satisfying $x = By$.

Sample 3
Input
1 2 1
1 0
0
1
Output
Yes

$\displaystyle \begin{array}{rcl} \displaystyle A &\displaystyle = &\displaystyle \left( \begin{array}{cc} 1 & 0 \end{array} \right) \\ \displaystyle B &\displaystyle = &\displaystyle \left( \begin{array}{c} 0 \\ 1 \end{array} \right) \\ \end{array} $

are the given matrices. Let $x$ be a $2$-dimensional column vector $x$ with real coefficients, and using real numbers $x_0, x_1$, write

$\displaystyle x = \left( \begin{array}{c} x_0 \\ x_1 \end{array} \right) \\ $

Since $Ax = (1 \cdot x_0 + 0 \cdot x_1) = (x_0)$, a necessary and sufficient condition for $Ax$ to be the zero vector is $x_0 = 0$.

If $x_0 = 0$, then defining the $1$-dimensional column vector $y$ with real coefficients as $(x_1)$ gives $x = By$. Conversely, if there exists a $1$-dimensional column vector $y$ with real coefficients satisfying $x = By$, then writing $y = (y_0)$ using a real number $y_0$, we get

$\displaystyle \left( \begin{array}{c} x_0 \\ x_1 \end{array} \right) = x = By = \left( \begin{array}{c} 0 \\ 1 \end{array} \right) (y_0) = \left( \begin{array}{c} 0 \\ y_0 \end{array} \right) $

so comparing the $1$st component shows that $x_0 = 0$. From the above, $x_0 = 0$ is equivalent to the existence of a $1$-dimensional column vector $y$ with real coefficients satisfying $x = By$. That is, $(A,B)$ is a good pair.

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