#163. 高斯消元 2

内存限制:256 MiB 时间限制:1500 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 1233b

题目描述

可能也是一道模板题。

给定稀疏矩阵 A ,以及列向量 b , 其中 A 的非零元素个数不超过 20000 ,求列向量 x 满足 Ax = b ,对 998244353 取模。

输入格式

第一行一个正整数 n ,表示矩阵大小。
接下来 n 行,每行 n + 1 个整数,其中第 i 行前 n 个整数第 j 个整数表示矩阵 A_{i, j} 的值,最后一个整数表示 b_i 的值。

输出格式

一行输出 n 个整数并对 998244353 取模。

样例

样例输入

3
1 2 0 5
0 1 4 14
2 0 1 5

样例输出

1 2 3

数据范围与提示

n \leq 2500 , 0 \leq A_{i, j}, b_i< 998244353 ,其中 A 中非零元素个数 \leq 20000 ,且 \text {rank} A = n