#P1914. Cramer's Rule

    ID: 915 传统题 1000ms 256MiB 尝试: 3 已通过: 1 难度: 7 上传者: 标签>线性代数TUD Programming Contest 2001DarmstadtGermany

Cramer's Rule

描述描述
背景
考虑一个线性方程组,这里以含三个变量x1x_1x2x_2x3x_3的三个方程为例。其一般形式如下,其中aija_{ij}bib_i为已知数:

a11x1+a12x2+a13x3=b1a_{11}x_1 + a_{12}x_2 + a_{13}x_3 = b_1
a21x1+a22x2+a23x3=b2a_{21}x_1 + a_{22}x_2 + a_{23}x_3 = b_2
a31x1+a32x2+a33x3=b3a_{31}x_1 + a_{32}x_2 + a_{33}x_3 = b_3

或用矩阵与向量表示为:

根据克莱姆法则,方程组的解可通过行列式表示,即:

xi=det(Ai)/det(A)x_i = \det(A_i)/\det(A)
其中AiA_i是将矩阵AA的第ii列替换为向量bb后得到的新矩阵。对于3×33 \times 3矩阵的行列式,可使用以下简单公式计算:

显然,克莱姆法则仅在det(A)0\det(A) \neq 0时适用。可以证明,当且仅当det(A)0\det(A) \neq 0时,方程组有唯一解;否则,方程组要么无解,要么有无穷多组解。

需要注意的是,求解大型线性方程组时通常不采用克莱姆法则,因为计算单个行列式的时间成本与使用更高效算法求解整个方程组的时间相当。

问题
给定一个三元线性方程组,若其存在唯一解,使用克莱姆法则求出该解。具体来说,需计算A1A_1A2A_2A3A_3AA的行列式,通过判断det(A)\det(A)是否为零来确定方程组是否有唯一解。若存在唯一解,按克莱姆法则计算并输出解。

输入
第一行包含测试用例的数量。
对于每个测试用例,包含三行数据,对应三个方程,矩阵AA的系数与向量bb的坐标按如下格式排列:

a11 a12 a13 b1a_{11} \ a_{12} \ a_{13} \ b_1
a21 a22 a23 b2a_{21} \ a_{22} \ a_{23} \ b_2
a31 a32 a33 b3a_{31} \ a_{32} \ a_{33} \ b_3
所有数值均为[1000,1000][-1000, 1000]范围内的整数,以空格分隔。

输出
每个测试用例输出三行内容:

  1. 第一行按顺序输出det(A1)\det(A_1)det(A2)\det(A_2)det(A3)\det(A_3)det(A)\det(A),整数之间用单个空格分隔。
  2. 第二行根据det(A)\det(A)的值输出:若行列式为零,输出"No unique solution";若行列式非零,输出"Unique solution: ",后跟x1x_1x2x_2x3x_3的值,保留三位小数,数值之间用单个空格分隔。对于满足0.0005<xi<0.0005-0.0005 < x_i < 0.0005的解,统一输出"0.000"(而非可能出现的"-0.000")。
  3. 第三行为空行。

输入数据

3
4 0 0 1
0 2 0 2
0 0 1 4
1 2 3 1
1 1 1 2
2 2 2 3
1 0 0 1
0 1 0 0
0 0 -1 0

输出数据

2 8 32 8
Unique solution: 0.250 1.000 4.000

1 -2 1 0
No unique solution

-1 0 0 -1
Unique solution: 1.000 0.000 0.000