2012 . 2017國手系列1：$N$元一次方程組
TopCoder
Description
在偏遠的競程地區中，有一個神秘人物叫做bb。沒有人知道「bb」這個名子的由來是甚麼，或者它代表甚麼意思，只知道它也許來自於某個古老的傳說。
出身於獨特背景的bb，受到上一代宗師的教導，他的實力是許多人難以想像的。據某些消息來源表示，bb可能是唯一一個在成為國手時還不會解二元一次聯立方程式的人物。然而，經過了短短的幾個月，現在輪到bb要考驗大家會不會解$N$元一次方程組了！
所謂的$N$元一次方程組，長得像這樣：
$\begin{align}
A_{1, 1}x_1 +& A_{1, 2}x_2 +& \cdots &&+ A_{1, N}x_N &= B_1 \newline
A_{2, 1}x_1 +& A_{2, 2}x_2 +& \cdots &&+ A_{2, N}x_N &= B_2 \newline
& \vdots & \ddots & && \vdots \newline
A_{N, 1}x_1 +& A_{N, 2}x_2 +& \cdots &&+ A_{N, N}x_N &= B_N \newline
\end{align}$
其中$A_{i,j}$和$B_i$都是常數。已知它恰有一組解，你能不能求出正確的$x_i$使上面每一條式子都成立呢？
Input Format
輸入第一行有一個正整數$T$，代表測資筆數。
對於每筆測資，第一行會有一個正整數$N$，代表你要解$N$元一次方程組。
接下來$N$行，每行有$N+1$個整數，第$i$行的數為$A_{i,1}, A_{i,2},\cdots ,A_{i,N-1},A_{i,N},B_i$。
對於所有測資，$T\leq 5; N\leq 600; |A_{i,j}|,|B_i|\leq 10^ 5$。
保證由 $A_{i,j}$ 所構成的矩陣中絕對值最大與最小的特徵值（eigenvalue）的比值 $\left|\frac{\lambda_1}{\lambda_N}\right|\leq 10^ 3$（白話地說，這組方程式不會太接近無解或沒有唯一解的方程式組）。
| 子任務(測資) | 額外限制 | 分數 |
|---|---|---|
| 1(0~2) | $N=1$ | 5 |
| 2(0~5) | $N\leq 2$ | 17 |
| 3(0~8) | $N\leq 3$ | 22 |
| 4(0~11) | $N\leq 5$ | 43 |
| 5(0~14) | $N\leq 20$ | 13 |
| 6(0~17) | $N\leq 80$ | 16 |
| 7(0~20) | $N\leq 200$ | 17 |
| 8(0~23) | 無限制 | 17 |
Output Format
對每筆測資請輸出$N$行，每行輸出一個浮點數（可以科學記號表示，如2.135e+7），第$i$行代表$x_i$的解。
考量到可能會有計算誤差，只要你輸出的$x_i$，對於方程組的每條式子，都有等號左右的相對或絕對誤差不超過$N\times 10^ {-7}$，就會被視為正確。
保證解的$|x_i|\leq 10^ 6$。
Sample Input 1
3
2 7 9 6
8 9 7 6
2 6 5 3
1
3 3
Sample Output 1
-3.191489362e-1
0.829787234
1
Hints
Problem Source
Problem Set / Description by Yihda Yol
建國中學106學年度校隊補選pA
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0~2 | 5 |
| 2 | 0~5 | 17 |
| 3 | 0~8 | 22 |
| 4 | 0~11 | 43 |
| 5 | 0~14 | 13 |
| 6 | 0~17 | 16 |
| 7 | 0~20 | 17 |
| 8 | 0~23 | 17 |