在偏遠的競程地區中，有一個神秘人物叫做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$使上面每一條式子都成立呢？
$N\le 600, |A_{i, j}|, |B_i|\le 10^5$
裸的高斯消去。
但直接寫後丟上去會吃wa，原因是精度爆掉。我嘗試過long double和__float128都會爆。
後來去問人得到一些建議:
- 為了讓除法能讓值變小，每次消去使用的值絕對值越大越好(Line 49)
- 把輸入給random shuffle。
然後就能ac了(? 甚至不用long double
複雜度還是一樣高斯消去的$\mathcal{O}(N^3)$，值得注意的是swap(std::vector, std::vector)是$\mathcal{O}(1)$的。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
|
#include <bits/stdc++.h>
using namespace std;
#define EmiliaMyWife ios::sync_with_stdio(0); cin.tie(NULL);
using ll = int64_t;
using ull = uint64_t;
using ld = long double;
using uint = uint32_t;
const double EPS = 1e-8;
const int INF = 0x3F3F3F3F;
const ll LINF = 4611686018427387903;
const int MOD = 1e9+7;
signed main() { EmiliaMyWife
cout << fixed << setprecision(15);
int t;
cin >> t;
mt19937 gen(time(NULL));
while(t--) {
int n;
cin >> n;
vector<vector<double>> arr(n, vector<double>(n + 1));
vector<int> xdd(n);
for(int i = 0; i < n; i++)
xdd[i] = i;
shuffle(xdd.begin(), xdd.end(), gen);
for(int i = 0; i < n; i++) {
vector<int> tmp(n);
for(int j = 0; j < n; j++)
cin >> tmp[j];
cin >> arr[i][n];
for(int j = 0; j < n; j++)
arr[i][xdd[j]] = tmp[j];
}
for(int i = 0; i < n; i++) {
for(int j = i; j < n; j++)
if(abs(arr[j][i]) > abs(arr[i][i]))
swap(arr[i], arr[j]);
for(int j = 0; j < n; j++) {
if(j == i)
continue;
for(int k = 0; k <= n; k++)
if(k != i)
arr[j][k] -= arr[i][k] * arr[j][i] / arr[i][i];
arr[j][i] = 0;
}
}
for(int i = 0; i < n; i++)
arr[i][n] /= arr[i][i];
for(int i = 0; i < n; i++)
cout << arr[xdd[i]][n] << '\n';
}
}
|