当前位置：首页 > news >正文

UVa 684 Integral Determinant

news 2026/7/17 20:58:03

题目描述

给定一个整数方阵（大小n≤30n \le 30n≤30），求其行列式。要求使用整数运算，避免浮点误差。输出每个行列式的值，最后输出一个单独的*表示结束。

输入格式

多组数据。每组第一行为一个整数nnn（n>0n > 0n>0），表示矩阵大小。接下来nnn行，每行nnn个整数，为矩阵元素。输入以n=0n = 0n=0结束。

输出格式

对于每个矩阵，输出一行行列式的值。最后输出一行*。

样例

输入

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。
- 若该行元素为负，则整行取反，并改变符号标志。
- 若该行不是当前行，则交换，并改变符号标志。
- 对下方的每一行j（i+1到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//// 版权所有（C）2021，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;intn;longlongg[32][32];longlongdeterminant(){longlongr=1;for(inti=0;i<n-1;i++){intoperated=0;do{intz=-1;for(intj=i;j<n;j++){if(g[j][i]<0){for(intk=i;k<n;k++)g[j][k]*=-1;r*=-1;}if(g[j][i]==1){z=j;break;}if(g[j][i]&&(z==-1||g[j][i]<g[z][i]))z=j;}if(z==-1)return0;if(z!=i){swap(g[i],g[z]);r*=-1;}operated=0;for(intj=i+1;j<n;j++)if(g[j][i]){operated=1;longlongc=g[j][i]/g[i][i];for(intk=i;k<n;k++)g[j][k]-=c*g[i][k];}}while(operated&&g[i][i]!=1);}for(inti=0;i<n;i++)r*=g[i][i];returnr;}intmain(){cin.tie(0),cout.tie(0),ios::sync_with_stdio(false);while(cin>>n,n){for(inti=0;i<n;i++)for(intj=0;j<n;j++)cin>>g[i][j];cout<<determinant()<<'\n';}cout<<"*\n";return0;}