UVa 684 Integral Determinant

题目描述给定一个整数方阵大小n≤30n \le 30n≤30求其行列式。要求使用整数运算避免浮点误差。输出每个行列式的值最后输出一个单独的*表示结束。输入格式多组数据。每组第一行为一个整数nnnn0n 0n0表示矩阵大小。接下来nnn行每行nnn个整数为矩阵元素。输入以n0n 0n0结束。输出格式对于每个矩阵输出一行行列式的值。最后输出一行*。样例输入2 5 2 3 4 3 2 3 5 1 6 7 4 8 9 0输出14 -27 *题目分析本题要求用整数运算计算行列式。直接按定义展开是O(n!)O(n!)O(n!)不可行。使用高斯消元法将矩阵化为上三角可以O(n3)O(n^3)O(n3)完成但涉及除法而本题要求整数精度不能使用浮点数。因此需要使用模意义下的高斯消元或整数高斯消元使用欧几里得算法进行行变换避免除法。代码中采用了一种变种通过行交换和行倍加将矩阵化为上三角并利用最小非零元作为主元逐步消去。由于矩阵元素可能为负数先对行取符号使主元为正然后通过行倍加减去主元的倍数消去下方元素。若主元不为111则通过交换找到绝对值最小的非零元并反复进行消去直到主元变为111或000。解题思路对每一列i从000到n−2n-2n−2在i到n-1行中寻找第i列非零且绝对值最小的行若全为零则行列式为000。若该行元素为负则整行取反并改变符号标志。若该行不是当前行则交换并改变符号标志。对下方的每一行ji1到n-1若g[j][i]非零则计算c g[j][i] / g[i][i]然后整行减去c倍的第i行。若主元g[i][i]不为111且仍有下方元素非零则重复上述过程。最后上三角矩阵对角线的乘积乘以符号即为行列式。注意该算法利用了整数除法但必须保证整除因此主元应尽量化为111否则可能需要更复杂的扩展欧几里得变换。代码中通过反复操作使主元变为111从而保证了整除。复杂度分析高斯消元O(n3)O(n^3)O(n3)n≤30n \le 30n≤30极快。代码实现// Integral Determinant// UVa ID: 684// Verdict: Accepted// Submission Date: 2021-12-01// UVa Run Time: 0.010s//// 版权所有C2021邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intn;longlongg[32][32];longlongdeterminant(){longlongr1;for(inti0;in-1;i){intoperated0;do{intz-1;for(intji;jn;j){if(g[j][i]0){for(intki;kn;k)g[j][k]*-1;r*-1;}if(g[j][i]1){zj;break;}if(g[j][i](z-1||g[j][i]g[z][i]))zj;}if(z-1)return0;if(z!i){swap(g[i],g[z]);r*-1;}operated0;for(intji1;jn;j)if(g[j][i]){operated1;longlongcg[j][i]/g[i][i];for(intki;kn;k)g[j][k]-c*g[i][k];}}while(operatedg[i][i]!1);}for(inti0;in;i)r*g[i][i];returnr;}intmain(){cin.tie(0),cout.tie(0),ios::sync_with_stdio(false);while(cinn,n){for(inti0;in;i)for(intj0;jn;j)cing[i][j];coutdeterminant()\n;}cout*\n;return0;}总结本题通过整数高斯消元法计算行列式避免了浮点误差。关键点包括使用行交换和行倍加操作保持整数运算。通过不断将主元化为111确保整除。注意符号变化行交换和行取反都会改变行列式符号。该解法是行列式计算的经典整数实现适用于n≤30n \le 30n≤30的规模。