代数余子式矩阵求行列式

发布时间:2017-7-1 11:47:07编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"代数余子式矩阵求行列式 ",主要涉及到代数余子式矩阵求行列式 方面的内容,对于代数余子式矩阵求行列式 感兴趣的同学可以参考一下。

因为在删除一条边时矩阵只有一行上的两个值发生变化,将上述法则代入该行即可。

#include <cstdio>#include <cmath>#define LL long long using namespace std;  int n,m;  LL sid[100001][3];  LL tot;  const LL mo=1e9+7;    LL qpow(LL bas,int powe){      LL ret=1;      for (;powe;bas*=bas,bas%=mo){        if (powe&1) ret*=bas,ret%=mo;      powe=powe>>1;        }    return(ret);  }      struct matrix{      LL a[601][601],tmp[601][601];      int n,m;            void cpy(matrix&b){        n=b.n;m=b.m;      for (int i=1;i<=n;i++)            for (int j=1;j<=m;j++)          a[i][j]=b.a[i][j];    }            void mul(matrix &b){      for (int i=0;i<=n;i++)         for (int j=0;j<=b.m;j++)           tmp[i][j]=0;              for (int i=0;i<=n;i++)        for (int k=0;k<=m;k++)          if (a[i][k])             for (int j=0;j<=b.m;j++)              tmp[i][j]+=a[i][k]*b.a[k][j]%mo,tmp[i][j]%=mo;              for (int i=0;i<=n;i++)        for (int j=0;j<=b.m;j++)          a[i][j]=tmp[i][j];      m=b.m;    }        LL det(){      for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) tmp[i][j]=a[i][j];      for (int i=1;i<=n;i++){        for (int j=i+1;j<=n;j++){          LL bas=a[j][i]*qpow(a[i][i],mo-2)%mo;          for (int k=i;k<=n;k++)            a[j][k]-=a[i][k]*bas%mo,a[j][k]%=mo,a[j][k]+=mo,a[j][k]%=mo;          }          }      LL ret=1;      for (int i=1;i<=n;i++) ret*=a[i][i],ret%=mo;      for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) a[i][j]=tmp[i][j];      return(ret);    }        void mul(LL num){      for (int i=1;i<=n;i++)        for (int j=1;j<=m;j++)          a[i][j]*=num,a[i][j]%=mo;    }        void getinv(){      for (int i=1;i<=n;i++) a[i][n+i]=1;      for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) a[i][j]=(a[i][j]%mo+mo)%mo;      for (int i=1;i<=n;i++){        int po;LL maxi=0;        for (int j=i;j<=n;j++){          if (fabs(a[j][i])>maxi){            maxi=fabs(a[j][i]);po=j;          }        }        for (int j=1;j<=2*n;j++){          LL t=a[i][j];a[i][j]=a[po][j];a[po][j]=t;        }        if (fabs(maxi)==0) continue;                    for (int j=i+1;j<=n;j++){          LL tim=a[j][i]*qpow(a[i][i],mo-2)%mo;          for (int k=i;k<=2*n;k++) a[j][k]-=a[i][k]*tim%mo,a[j][k]%=mo;          }        }                for (int i=1;i<=n;i++) for (int j=1;j<=2*n;j++) a[i][j]=(a[i][j]%mo+mo)%mo;        for (int i=n;i>=1;i--){          for (int j=i+1;j<=n;j++){            for (int k=n+1;k<=2*n;k++)              a[i][k]-=a[i][j]*a[j][k]%mo,a[i][k]%=mo;            a[i][j]=0;                    }          for (int j=n+1;j<=2*n;j++)            a[i][j]*=qpow(a[i][i],mo-2),a[i][j]%=mo;          a[i][i]=1;          }                for (int i=1;i<=n;i++)          for (int j=1;j<=n;j++)            a[i][j]=(a[i][j+n]%mo+mo)%mo;    }        void trav(){      for (int i=1;i<=n;i++)        for (int j=1;j<=n;j++)          tmp[i][j]=a[j][i];      for (int i=1;i<=n;i++)        for (int j=1;j<=n;j++)          a[i][j]=tmp[i][j];    }  }a,A,inv;  int main(){            scanf("%d%d",&n,&m);      a.n=a.m=n-1;      for (int i=1;i<=m;i++){        scanf("%lld%lld%lld",&sid[i][0],&sid[i][1],&sid[i][2]);        a.a[sid[i][0]][sid[i][1]]--;        a.a[sid[i][0]][sid[i][0]]++;    }    A.n=A.m=n-1;    for (int i=1;i<n;i++) A.a[i][i]=1;    A.mul(tot=a.det());        inv.cpy(a);    inv.getinv();    A.mul(inv);    A.trav();        LL ans=0;    for (int i=1;i<=m;i++){      if (sid[i][0]==n) continue;      a.a[sid[i][0]][sid[i][1]]++;        a.a[sid[i][0]][sid[i][0]]--;      LL ttot=0;      for (int j=1;j<n;j++)        ttot+=a.a[sid[i][0]][j]*A.a[sid[i][0]][j]%mo,ttot%=mo;      ans+=(tot-ttot)*sid[i][2]%mo;ans%=mo;       a.a[sid[i][0]][sid[i][1]]--;        a.a[sid[i][0]][sid[i][0]]++;    }    printf("%lld\n",(ans%mo+mo)%mo);  }


上一篇:java术语(PO/POJO/VO/BO/DAO/DTO)
下一篇:HDU - 5410 CRB and His Birthday

相关文章

相关评论

本站评论功能暂时取消,后续此功能例行通知。

一、不得利用本站危害国家安全、泄露国家秘密,不得侵犯国家社会集体的和公民的合法权益,不得利用本站制作、复制和传播不法有害信息!

二、互相尊重,对自己的言论和行为负责。

好贷网好贷款