C++11(clang++ 3.9) 解法, 执行用时: 91ms, 内存消耗: 728K, 提交时间: 2019-10-04 16:40:09
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN=205;
const int Mod=1000000007;
int a[MAXN][MAXN],b[MAXN][MAXN];
int fp(int a,int k) {
int res=1;
while(k) {
if(k&1)res=1LL*res*a%Mod;
a=1LL*a*a%Mod;
k>>=1;
}
return res;
}
void solve(int n) {
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
b[i][j]=(i==j);
int det=1;
for(int i=1; i<=n; i++) {
int t=i;
for(int k=i; k<=n; k++)
if(a[k][i])t=k;
if(t!=i)det*=-1;
for(int j=1; j<=n; j++) {
swap(a[i][j],a[t][j]);
swap(b[i][j],b[t][j]);
}
det=1LL*a[i][i]*det%Mod;
int inv=fp(a[i][i],Mod-2);
for(int j=1; j<=n; j++) {
a[i][j]=1LL*inv*a[i][j]%Mod;
b[i][j]=1LL*inv*b[i][j]%Mod;
}
for(int k=1; k<=n; k++) {
if(k==i)continue;
int tmp=a[k][i];
for(int j=1; j<=n; j++) {
a[k][j]=(a[k][j]-1LL*a[i][j]*tmp%Mod+Mod)%Mod;
b[k][j]=(b[k][j]-1LL*b[i][j]*tmp%Mod+Mod)%Mod;
}
}
}
det=(det+Mod)%Mod;
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
b[i][j]=1LL*det*b[i][j]%Mod;
}
int main() {
int n;
while(scanf("%d",&n)!=EOF) {
for(int j=1; j<=n; j++)
a[1][j]=2;
for(int i=2; i<=n; i++)
for(int j=1; j<=n; j++)
scanf("%d",&a[i][j]);
solve(n);
for(int i=1; i<=n; i++)
printf("%d%c",(i&1 ? b[i][1] : (Mod-b[i][1])%Mod)," \n"[i==n]);
}
return 0;
}
C++14(g++5.4) 解法, 执行用时: 456ms, 内存消耗: 2072K, 提交时间: 2019-10-05 15:22:57
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll mod=1e9+7;
const int maxn=300+10;
ll a[maxn][maxn],b[maxn][maxn];
int n;
ll qpow(ll a,ll b)
{
ll rec=1;
while(b){
if(b&1) rec=rec*a%mod;
a=a*a%mod;
b>>=1;
}
return rec;
}
void work()
{
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++)
b[i][j]=(i==j);
}
ll det=1;
for(int i=1;i<=n;i++){
int t=i;
for(int k=i;k<=n;k++){
if(a[k][i]) t=k;
}
if(i!=t) det=-det;
for(int j=1;j<=n;j++){
swap(a[i][j],a[t][j]);
swap(b[i][j],b[t][j]);
}
det=a[i][i]*det%mod;
ll inv=qpow(a[i][i],mod-2);
for(int j=1;j<=n;j++){
a[i][j]=a[i][j]*inv%mod;
b[i][j]=b[i][j]*inv%mod;
}
for(int k=1;k<=n;k++){
if(k==i) continue;
ll temp=a[k][i];
for(int j=1;j<=n;j++){
a[k][j]=(a[k][j]-a[i][j]*temp%mod+mod)%mod;
b[k][j]=(b[k][j]-b[i][j]*temp%mod+mod)%mod;
}
}
}
det=(det+mod)%mod;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
b[i][j]=b[i][j]*det%mod;
}
}
}
int main()
{
while(~scanf("%d",&n)){
for(int i=1;i<=n;i++)
a[1][i]=2;
for(int i=2;i<=n;i++){
for(int j=1;j<=n;j++)
scanf("%lld",&a[i][j]);
}
work();
for(int i=1;i<=n;i++){
if(i&1)
printf("%lld",b[i][1]);
else
printf("%lld",(mod-b[i][1])%mod);
if(i!=n) printf(" ");
else printf("\n");
}
}
}
C++(g++ 7.5.0) 解法, 执行用时: 46ms, 内存消耗: 712K, 提交时间: 2022-08-22 13:03:46
#include<bits/stdc++.h>
using namespace std;
const int N = 205;
const int mod = 1e9 + 7;
typedef long long ll;
ll qpow(ll x,ll y){
ll res = 1;
while(y){
if(y&1) res = res*x%mod;
x = x*x%mod;
y>>=1;
}
return res;
}
ll A[N][N],n,sgn=1;
void Gauss(int n){
int r = 1;
for(int c=1;c<=n;c++,r++){
for(int i=r+1;i<=n;i++)
if(A[i][c] != 0) swap(A[r],A[i]),sgn=sgn*(mod-1)%mod;
if(A[r][c] == 0) {r--;continue;}
for(int i=1;i<=n;i++){
if(i==r) continue;
ll tmp = A[i][c] * qpow(A[r][c],mod-2)%mod;
for(int j=c;j<=n+1;j++)
A[i][j] =(A[i][j] - A[r][j] * tmp%mod + mod) % mod;
}
}
}
int main(){
while(~scanf("%lld",&n)){
sgn = 1;
for(int i=1;i<n;i++)
for(int j=1;j<=n;j++) scanf("%lld",&A[i][j]);
Gauss(n-1);
for(int i=1;i<n;i++){
ll ans = sgn *((n-1-i)&1 ? (mod-1):1)%mod;
for(int j=1;j<n;j++){
if(j == i) ans*=A[j][n],ans%=mod;
else ans*=A[j][j],ans%=mod;
}
printf("%lld ",ans);
}
ll ans = sgn;
for(int j=1;j<n;j++)
ans = (ans * A[j][j])%mod;
printf("%lld\n",ans);
}
}
)
of matrix A in ICPCCamp. He also knew determinant can be computed in )
using Gaussian Elimination.%20%5Ctimes%20n)
matrix B he would like to find )
modulo )
for all 
is the matrix after removing the j-th column from B..