题解 P2455 【[SDOI2006]线性方程组】
由线性代数知识，我们知道，对于
- 若
\mathrm R(\boldsymbol A,\boldsymbol \beta)=\mathrm R(\boldsymbol A)=r ，且r=n 时，原方程有唯一解 - 若
\mathrm R(\boldsymbol A,\boldsymbol \beta)=\mathrm R(\boldsymbol A)=r ，且r<n 时，原方程有无穷多解 - 若
\mathrm R(\boldsymbol A,\boldsymbol \beta)\not =\mathrm R(\boldsymbol A) 时，原方程无解
然后我们直接模拟即可，用高斯-约旦消元法把增广矩阵化成行最简形矩阵。
我这里写了一个class封装了一下，利用了STL中的valarray。另外代码中含有不少C++11+的特性，在NOIP等环境需要把auto换成相应的类型。
template <typename T>
class mat
{
int r, c; // 行，列
bool simplified = false; // 记录是否已化简
valarray<T> data; // 用valarray存储数据
public:
mat(int r, int c) : r(r), c(c), data(r * c) {}
// M(i, j)可取第i行第j列的元素
T &operator()(int i, int j) { return data[i * c + j]; }
// M[i]可取第i行的切片
auto operator[](int i) { return data[slice(i * c, c, 1)]; }
// M(i)可取第i列的切片
auto operator()(int i) { return data[slice(i, r, c)]; }
// 交换两行
void rswap(int r1, int r2)
{
for (int i = 0; i < c; ++i)
swap((*this)(r1, i), (*this)(r2, i));
}
// 接下来是重点，进行行变换，把矩阵变成行最简形矩阵
mat<T> &simplify()
{
int curr = 0; // 当前行
auto &M = *this;
for (int i = 0; i < c && curr < r; ++i) // 枚举列
{
int maxr = curr; // 找到该列（剩余的）最大元素所在的行
for (int j = curr + 1; j < r; ++j)
if (M(j, i) > M(maxr, i))
maxr = j;
if (M(maxr, i) == 0) // 该列剩余元素全为0，跳到下一列
continue;
rswap(maxr, curr); // 把最大元素所在行交换到当前行处
M[curr] /= valarray<T>(M(curr, i), c); // 令最大元素归一
valarray<T> line = M[curr];
for (int j = 0; j < r; ++j) // 用当前行对其余行进行消元
if (j != curr)
M[j] -= line * M(j, i);
curr++;
}
simplified = true;
return *this;
}
// 从第L列到第R列（左闭右开）的子矩阵的秩
int rank(int L, int R)
{
// 如果还未化为行最简形矩阵，就复制一下当前矩阵，并化简
mat &M = (simplified ? *this : mat(*this).simplify());
int cnt = 0;
for (int i = 0; i < r; ++i) // 统计非0行
{
bool allzero = true;
for (int j = L; j < R; ++j)
if (M(i, j) != 0)
allzero = false;
cnt += !allzero;
}
return cnt;
}
int rank() { return rank(0, c); }
};主函数就不写了，按照上面给出的定理很容易实现。只是有个细节可以注意一下：输出的时候可能会输出-0.00，所以可以把要输出的数加上一个很小的实数（如1e-6）再输出。