Problems Submissions
Register Login 質問(Gitter) GitHub

System of Linear Equations

AC一覧

問題

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

制約

入力

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

出力

解が存在しない場合

-1

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

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

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

サンプル

# 1

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

Forum


Timelimit: 5 secs