spoj2832 DETER3 [Matrix-Tree定理+模意义下矩阵行列式]

in 题目 with 0 comment

Description

Given a NxN matrix A, find the Determinant of A % P.


Input

Multiple test cases (the size of input file is about 3MB, all numbers in each matrix are generated randomly).
The first line of every test case contains two integers , representing N ($0 < N < 201$) and P ($0 < P < 1,000,000,001$). The following N lines each contain N integers, the j-th number in i-th line represents A[i][j] ($- 1,000,000,001 < A[i][j] < 1,000,000,001$).


Output

For each test case, print a single line contains the answer.


Sample Input

1 10
-528261590
2 2
595698392 -398355861
603279964 -232703411
3 4
-840419217 -895520213 -303215897
537496093 181887787 -957451145
-305184545 584351123 -257712188


Sample Output


Solution

这道题是模意义下矩阵行列式模板题,由于同余的性质只适用于加法,减法和乘法,而不适用于除法,所以不能用高斯消元对这类问题求解,但是消元的方法很多,我们不妨用辗转相除法进行,具体的过程可以参考: http://blog.csdn.net/u013010295/article/details/47451451


Code

#include<bits/stdc++.h>
#define maxn 250
#define eps 1e-6
// #define DEBUG
using namespace std;
int n,mod;
long long a[maxn][maxn];

inline int dcmp(long long a)
{
  if(fabs(a)<eps) return 0;
  else return a>0?1:-1;
}

inline long long read()
{
  char ch;
  int sign=1;
  long long read=0;
  do
    ch=getchar();
  while((ch<'0'||ch>'9')&&ch!='-');
  if(ch=='-') sign=-1,ch=getchar();
  while(ch>='0'&&ch<='9')
  {
    read=read*10+ch-'0';
    ch=getchar();
  }
  return 1ll*sign*read;
}

void init()
{
  memset(a,0,sizeof(a));
  for(int i=1;i<=n;++i)
    for(int j=1;j<=n;++j)
    {
      a[i][j]=read();
      if(a[i][j]<0)
      {
        int x=(-a[i][j])/mod;
        a[i][j]=(a[i][j]+1ll*(x+1)*mod)%mod;
      }
      else a[i][j]%=mod;
    }
#ifdef DEBUG
  for(int i=1;i<=n;++i){
    for(int j=1;j<=n;++j)
      cout<<a[i][j]<<" ";
    cout<<endl;}
#endif
}

void det()
{
  if(n==1)
  {
    printf("%lld\n",a[1][1]);
    return ;
  }
  int rev=0;
  for(int i=1;i<=n;++i)
  {
    if(!dcmp(a[i][i]))
    {
      int k=i;
      while(!dcmp(a[k][k])) k++;
      swap(a[k],a[i]);
      rev^=1;
    }
    for(int j=i+1;j<=n;++j)
    {
      while(a[j][i]!=0)
      {
        int x=a[j][i]/a[i][i];
        if(x!=0)
        {
          for(int k=i;k<=n;++k)
          {
            a[j][k]-=(long long)(a[i][k]*x)%mod;
            if(a[j][k]<0) a[j][k]+=mod;
          }
        }
        else
        {
          swap(a[i],a[j]);
          rev^=1;
        }
      }
    }
  }
  long long ans=1;
  for(int i=1;i<=n;++i) ans=ans*a[i][i]%mod;
  if(rev) ans=(mod-ans)%mod;
  printf("%lld\n",ans);
}

int main()
{
  while(scanf("%d%d",&n,&mod)==2)
  {
    init();
    det();
  }
}

/*
3 121
-1231923 -12893719 213810
123 -239797 -37912739
-189237 2380213 -123123
*/

扫描二维码,在手机上阅读!
Responses