CSES 3154 - System of Linear Equations

給定 \(n\cdot(m+1)\) 個係數 \(a_{i,j}\) 與 \(b_i\)，它們構成以下 \(n\) 條線性方程式：

• \(a_{1,1}x_1 + a_{1,2}x_2 + \dots + a_{1,m}x_m = b_1 \pmod {10^9 + 7}\)
• \(a_{2,1}x_1 + a_{2,2}x_2 + \dots + a_{2,m}x_m = b_2 \pmod {10^9 + 7}\)
• \(\dots\)
• \(a_{n,1}x_1 + a_{n,2}x_2 + \dots + a_{n,m}x_m = b_n \pmod {10^9 + 7}\)

你的任務是找出任意 \(m\) 個整數 \(x_1, x_2, \dots, x_m\)，使它們滿足上面給定的方程式。

輸入格式

第一行有兩個整數 \(n\) 和 \(m\)：方程式的數量與未知數的數量。

接下來 \(n\) 行，每行有 \(m+1\) 個整數 \(a_{i,1}, a_{i,2}, \dots, a_{i,m}, b_i\)：第 \(i\) 條方程式的係數。

輸出格式

輸出 \(m\) 個整數 \(x_1, x_2,\dots, x_m\)：滿足這些方程式的未知數的值。這些值還必須滿足 \(0 \le x_i < 10^9 + 7\)。只要是合法的答案都可以輸出。若不存在任何解，則只輸出 \(-1\)。

範例輸入 1

3 3
2 0 1 7
1 2 0 0
1 3 1 2

範例輸出 1

2 1000000006 3

限制

• \(1 \le n, m \le 500\)
• \(0 \le a_{i,j}, b_i < 10^9 + 7\)

題目來源

CSES - System of Linear Equations

題目來自 CSES Problem Set（Antti Laaksonen），授權 CC BY-NC-SA 4.0；本頁為翻譯，以相同授權分享。