首页 > ACM题库 > HDU-杭电 > HDU 2827-The Evaluation of Determinant-数论-[解题报告]HOJ
2014
02-17

HDU 2827-The Evaluation of Determinant-数论-[解题报告]HOJ

The Evaluation of Determinant

问题描述 :

The determinant is quite important in Linear Algebras, but I think that almost everyone who has ever learnt Linear Algebras is tired of the complicated and tedious calculations of determinant. Actually, it’s not the job we should do, isn’t it? As an outstanding Geek, why don’t we just ask computers to do these?

Give you a determinant D (it’s ensured that the result of it is an integer) and m, try to get the result of this determinant mod m, and m = p1 * p2 …… pn, all the pi are different. You can assume 1000 < pi < 10000, aij < 1000, and m can be fit in 32-bit signed integer.

输入:

Input two integers n and m in the first line, n represents the scale of the determinant. (n <= 100)
Then comes an n * n matrix, the determinant’s component aij means the one in row i and column j.

输出:

Input two integers n and m in the first line, n represents the scale of the determinant. (n <= 100)
Then comes an n * n matrix, the determinant’s component aij means the one in row i and column j.

样例输入:

2 1009
1 2
3 4

样例输出:

1007

这题卡了我一个晚上+一个早上,恶心的不想吐槽,一开始想法是直接高斯消元求解,但是wa了一个晚上,应该是哪里爆了int64,后来去看题目,发现了一个条件,就是m可以划分成很多个Pi相乘,1000<Pi<10000,这个条件给了我新的想法,直接对每个Pi求解,得到的就是|A|%pi的值,那么对于每个Pi都有一个余数,这就是中国剩余定理了,很不错的一个模板题,同时测试我几个模板,wa了我好多次,传址搞错了,坑爹阿。

6010521 2012-05-28 14:14:02 Accepted 2827 484MS 704K 2928 B G++ Sadly_Snoopy
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#define LL long long
using namespace std;
 LL n,m,A[105][105],p[10000],pos,d[105],r[105],len,B[105][105];
 bool vd[10005]={0};
 void prime()
{
    pos=0;
    for(int i=2;i<10005;i++)
    {
        if(!vd[i])
        {
           if(i>1000) p[pos++]=i;
            for(int j=(i<<1);j<10005;j+=i)
                vd[i]=1;
        }
    }
}
void deal(LL k)
{
    len=0;
    for(int i=0;i<pos&&k!=1;i++)
    {
        if(k%p[i]==0)
        {
            while(k%p[i]==0)
            {
                d[len++]=p[i];
                k/=p[i];
            }
        }
    }
}
LL exp(LL a,LL b,LL mod)
{
    LL ans=1;
    while(b)
    {
        if(b&1)ans=ans*a%mod;
        a=a*a%mod;b>>=1;
    }
    return ans;
}
void ex_gcd(LL a,LL b,LL &dd,LL &x,LL &y)
{
    if(b==0)
        x=1,y=0,dd=a;
    else
    {
        ex_gcd(b,a%b,dd,y,x);
        y-=x*(a/b);
    }
}
LL gauss(LL mod)
{
    bool flag=0;
    LL ans=1;
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            B[i][j]=A[i][j];
    for(int k=0;k<n-1;k++)
    {
        LL max_b=B[k][k];int bin=k;
        for(int i=k+1;i<n;i++)
            if(B[i][k]>max_b)
                max_b=B[i][k],bin=i;
        if(bin!=k)
        {
            for(int i=k;i<n;i++)
                swap(B[bin][i],B[k][i]);
            flag^=1;
        }
        if(B[k][k]<0)B[k][k]+=mod;
        LL Ni,y,dd;
        ex_gcd(B[k][k],mod,dd,Ni,y);
        Ni%=mod;
        if(Ni<0)Ni+=mod;
        for(int j=k+1;j<n;j++)
        {
            B[k][j]=B[k][j]*Ni%mod;
            if(B[k][j]<0)B[k][j]+=mod;
            for(int i=k+1;i<n;i++)
            {
                B[i][j]=(B[i][j]-(B[k][j]*B[i][k])%mod)%mod;
                if(B[i][j]<0)B[i][j]+=mod;
            }
        }
        ans*=B[k][k];
        ans%=mod;
        if(ans<0)ans+=mod;
    }
    ans*=B[n-1][n-1];
    ans%=mod;
    if(flag)ans=-ans;
    if(ans<0)ans+=mod;
    return ans;
}

LL china_remain()
{
    LL a,b,c,c1,c2,x,y,dd,N;
    a=d[0],c1=r[0];
    if(c1==0)c1=d[0];
    for(int i=1;i<len;i++)
    {
        b=d[i],c2=r[i];
        ex_gcd(a,b,dd,x,y);
        c=c2-c1;
        LL b1=b/dd;
        x=((c/dd*x)%b1+b1)%b1;
        c1=a*x+c1;
        a=a*b1;
    }
    return c1%m;
}
int main()
{
    prime();
    while(cin>>n>>m)
    {
        deal(m);
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++)
                cin>>A[i][j];
        if(m==1)
        {
            cout<<0<<endl;
            continue;
        }
        for(int i=0;i<len;i++)
        {
            r[i]=gauss(d[i]);
        }
        cout<<china_remain()<<endl;
    }
    return 0;
}

解题参考:http://blog.csdn.net/xymscau/article/details/7609138


  1. 可以根据二叉排序树的定义进行严格的排序树创建和后序遍历操作。如果形成的排序树相同,其树的前、中、后序遍历是相同的,但在此处不能使用中序遍历,因为,中序遍历的结果就是排序的结果。经在九度测试,运行时间90ms,比楼主的要快。