TOJ4537: n阶行列式

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

TOJ

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

#include<iostream>

using namespace std;

__int64 det(__int64 *a, int n)

{

    int i,j,m,c;

    --n;

    __int64 s=,b[n*n];

    if(n==)return a[];

    for(m=; m<=n+; m++)

    {

        c=;

        for(i=; i<=n; i++)

            for(j=; j<=n; j++)

                if(!(i==||(j+)==m))

                    b[c++]=a[i*n+j+i];

        if((m+)%)

            s+=-*a[m-]*det(b,n);

        else

            s+=a[m-]*det(b,n);

    }

    return s;

}

int main()

{

    __int64 a[];

    int ca=,n,i,j;

    while(cin>>n,n)

    {

        for(i=; i<n; i++)

            for(j=; j<n; j++)

                cin>>a[i*n+j];

        cout<<"case"<<ca++<<": D="<<det(a,n)<<".\n\n";

    }

    return ;

}

化简成上三角行列式的

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

ll a[][];

ll det(int n)

{

    ll ans=;

    int sign=;

    for(int i=; i<n; i++) //当前行

    {

        for(int j=i+; j<n; j++) //当前之后的每一行，因为每一行的当前第一个数要转化成0（想想线性代数中行列式的计算）

        {

            int x=i,y=j;

            while(a[y][i])//利用gcd的方法，不停地进行辗转相除

            {

                ll t=a[x][i]/a[y][i];

                for(int k=i; k<n; k++)

                    a[x][k]=a[x][k]-a[y][k]*t;

                swap(x,y);

            }

            if(x!=i)//奇数次交换，则D=-D'整行交换

            {

                for(int k=; k<n; k++)swap(a[i][k],a[x][k]);

                sign^=;

            }

        }

        if(a[i][i]==)//斜对角中有一个0，则结果为0

        {

            return ;

        }

        else

            ans=ans*a[i][i];

    }

    if(sign)ans*=-;

    return ans;

}

int main()

{

    int ca=,n,i,j;

    while(cin>>n,n)

    {

        for(i=; i<n; i++)

            for(j=; j<n; j++)

                cin>>a[i][j];

        cout<<"case"<<ca++<<": D="<<det(n)<<".\n\n";

    }

    return ;

}