http://www.tsinsen.com/

清橙网格自动评测系统

>> 用户名或邮箱:   密码:       忘记密码   其他登录:
 
 
 
A1079. 行列式计算
时间限制:1.0s   内存限制:512.0MB  
总提交次数:1079   AC次数:555   平均分:68.04
将本题分享到:
   
 
问题描述
  给出一个n阶行列式A,计算它的值。(3<=n<=5)
  要计算n阶行列式的值,可以按下面的方法:
  1. 设s=0。
  2. 枚举所有1至n个数的排列(参照01序列、枚举字串等题),对于它的每一个排列P(1)..P(n),求它的逆序对个数(见逆序对个数一题)t,然后将所有的A[i,P(i)]相乘得到乘积M,如果逆序对个数为偶数,则将s加上M,否则将s减去M。
  例如,要计算下面行列式的值:
  1 2 3
  3 2 1
  5 1 3
  则枚举所有的排列,当n=3时共有6个排列,它们是:
  1 2 3
  1 3 2
  2 1 3
  2 3 1
  3 1 2
  3 2 1
  对于每一个排列,可以计算一个乘积M和逆序对的个数t:
  1 2 3: M=A[1,1]*A[2,2]*A[3,3]=1*2*3=6, t=0
  1 3 2: M=A[1,1]*A[2,3]*A[3,2]=1*1*1=1, t=1
  2 1 3: M=A[1,2]*A[2,1]*A[3,3]=2*3*3=18, t=1
  2 3 1: M=A[1,2]*A[2,3]*A[3,1]=2*1*5=10, t=2
  3 1 2: M=A[1,3]*A[2,1]*A[3,2]=3*3*1=9, t=2
  3 2 1: M=A[1,3]*A[2,2]*A[3,1]=3*2*5=30, t=3
  所以结果为:s=6-1-18+10+9-30=-24
  以我们现在的知识,要枚举1至n的排列比较困难,我们可以把行列式扩展一下,在右下角加入一个单位矩阵,使之变为一个5阶的矩阵,上面的矩阵变为:
  1 2 3 0 0
  3 2 1 0 0
  5 1 3 0 0
  0 0 0 1 0
  0 0 0 0 1
  这样变化的好处是小于5阶的矩阵变为了5阶的矩阵,而且行列式的值不变,我们只需要能枚举1至5的排列就可以解决问题了。
提示
  所谓1至n的排列,是指由1至n这n个数组成的一个序列P(1)..P(n),在这个序列中,1至n中的每一个整数出现且仅出现一次,要生成5个数的排列,可以按照“枚举字串”的方法先生成5个数的序列,然后判断是不是每个数都只出现了一次(即没有重复出现的数字)。
  你可以将以前自己写过的代码拿来进行拼凑后作为本题的代码。按照开卷考试的要求,你可以参考或引用你自己带到考场的资料,包括以前在评测系统上做的题。
输入格式
  第一行只有一个整数n,为行列式的阶数,第2行到第n+1行,每行n个整数,为需要计算的n阶行列式。
输出格式
  仅输出一个整数,为行列式的值。
样例输入
3
1 2 3
2 3 1
3 1 2
样例输出
-18
样例输入
3
1 2 3
3 2 1
5 1 3
样例输出
-24