System of Linear Equations

AC一覧

Problem Statement
問題文

Given $N \times M$ matrix $A$, a size $N$ vector $b$. Please calculate a (size $M$) vector $b$ s.t. $Ax = b$. We consider everything $\mathbb{Z}_{998244353}$.

$N \times M$ 行列 $A$, 長さ $N$ のベクトル $b$ が与えられます。$Ax = b$ を満たす(長さ $M$ の)ベクトル $x$ を求めてください。ただし全ての要素は $\mathbb{Z}_{998244353}$ で考えることとします。

Constraints
制約

Input
入力

$N$ $M$
$A_{0,0}$ $A_{0,1}$ ... $A_{0,M-1}$
$A_{1,0}$ $A_{1,1}$ ... $A_{1,M-1}$
:
$A_{N-1,0}$ $A_{N-1,1}$ ... $A_{N-1,M-1}$
$b_0$ $b_1$ ... $b_{N-1}$

Output
出力

If there is no solution, print

解が存在しない場合

-1

and if exists, print as follows.

と出力してください。存在する場合、

$R$
$c_0$ $c_1$ ... $c_{M-1}$
$d_{0,0}$ $d_{0,1}$ ... $d_{0,M-1}$
:
$d_{R-1,0}$ $d_{R-1,1}$ ... $d_{R-1,M-1}$

We note that $R$ is the rank of solution. $c_i$ is one of the solution. For each $j$, $d_{j,0}, ..., d_{j,M-1}$ is the basis of solution.

と出力してください。ただし、$R$ は解空間の次元、$c_i$ は解のうち $1$ つとし、各 $j$ について、$d_{j,0}, ..., d_{j,M-1}$ は解空間の(それぞれ独立な)基底ベクトルとします。

Sample
サンプル

# 1

2 3
1 2 3
4 5 6
50 122
1
998244351 26 0
1 998244351 1

Forum


Timelimit: 5 secs

Before submitting, please confirm terms and conditions