4537: n阶行列式 

Time Limit(Common/Java):1000MS/3000MS     Memory Limit:65536KByte

Total Submit: 28            Accepted:3

Description

 

设有n²个数，排列成n行n列的表

    其中p1,p2,p3,...,pn是1到n的一个全排列。标准次序是从小到大。

注意在这n个元素的任一排列中，当两个元素的先后次序与标准次序不同时，就说有一个逆序，一个排列中所有逆序的总和叫做这个排列的逆序数。逆序数为奇数的排列叫做奇排列，反之为偶排列。τ为当前排列的逆序数。

     

 

 

 

Input

 

 

每组数据一个n，接下来有n*n个数据。0<n<10。输入直到n为0结束。

 

 

Output

 

 

对于每组数据，输出n阶行列式D的值，每组数据后一换行。

 

 

 

Sample Input

 

2

3 -2

2 1

0

Sample Output

 case1: D=7.

Source

我提供了两种写法，一种是其可以暴力算，但是复杂度还是挺高的

 

#include
       
        using namespace std;__int64 det(__int64 *a, int n){    int i,j,m,c;    --n;    __int64 s=0,b[n*n];    if(n==0)return a[0];    for(m=1; m<=n+1; m++)    {        c=0;        for(i=0; i<=n; i++)            for(j=0; j<=n; j++)                if(!(i==0||(j+1)==m))                    b[c++]=a[i*n+j+i];        if((m+1)%2)            s+=-1*a[m-1]*det(b,n);        else            s+=a[m-1]*det(b,n);    }    return s;}int main(){    __int64 a[105];    int ca=1,n,i,j;    while(cin>>n,n)    {        for(i=0; i
        
         >a[i*n+j];        cout<<"case"<
         
          <<": D="<
          
           <<".\n\n";    }    return 0;}
          
         
        
       

 

化简成上三角行列式的

#include
       
        using namespace std;typedef long long ll;ll a[20][20];ll det(int n){    ll ans=1;    int sign=0;    for(int i=0; i
        
         >n,n)    {        for(i=0; i
         
          >a[i][j];        cout<<"case"<
          
           <<": D="<
           
            <<".\n\n";    }    return 0;}