3434 . [模板題] System of Linear Equations
TopCoder
Tags
Description
Given $N \times M$ matrix $A$, a size $N$ vector $b$. Please calculate a (size $M$) vector $x$ s.t. $Ax = b$. We consider everything $\mathbb{F}_ {998244353}$.
Input Format
$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 Format
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.
Sample Input 1
2 3 1 2 3 4 5 6 50 122
Sample Output 1
1 998244351 26 0 1 998244351 1
Hints
- $1 \leq N, M \leq 500$
- $0 \leq A_ {ij} < 998244353$
Problem Source
Subtasks
| No. | Testdata Range | Score |
|---|