QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#743037#7612. Matrix InverseyanshanjiahongWA 337ms96716kbC++233.8kb2024-11-13 18:01:222024-11-13 18:01:22

Judging History

你现在查看的是最新测评结果

  • [2024-11-13 18:01:22]
  • 评测
  • 测评结果:WA
  • 用时:337ms
  • 内存:96716kb
  • [2024-11-13 18:01:22]
  • 提交

answer

#include<bits/stdc++.h>
#define rep(i,j,k) for(int i=j;i<=k;i++)
#define repp(i,j,k) for(int i=j;i>=k;i--)
#define ls(x) (x<<1)
#define rs(x) ((x<<1)|1)
#define mp make_pair
#define sec second
#define fir first
#define pii pair<int,int>
#define lowbit(i) i&-i
#define double long double
#define int long long
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N=2005,M=15,S=(1<<8)+5,inf=(ll)1e18+7,mo=1e9+7;
const double eps=1e-8;
void read(int &p){
	int x=0,w=1;
	char ch=0;
	while(!isdigit(ch)){
		if(ch=='-')w=-1;
		ch=getchar();
	}
	while(isdigit(ch)){
		x=(x<<1)+(x<<3)+ch-'0';
		ch=getchar();
	}
	p=x*w;
}
int quick_power(int base,int x){
    int res=1;
    while(x){
        if(x&1)res*=base,res%=mo;
        base*=base,base%=mo;
        x>>=1;
    }
    return res;
}
int n,a[N][N],b[N][N],rdm[N],resm[N];
vector<int>inch,incl;
bool wrh[N],wrl[N];
mt19937 rd(time(0));
int k[N][N];
int rdn(int x,int y){
    return rd()%(y-x+1)+x;
}
int gres[N];
void gauss(int numx){
    rep(i,1,numx){
        int r=i;
        rep(j,i+1,n)
            if(k[j][i]>k[r][i])r=j;
        swap(k[i],k[r]);
        int div=k[i][i],invd=quick_power(div,mo-2);
        //printf("!!!%lld %lld\n",div,invd);
        rep(j,i,numx+1)
            k[i][j]*=invd,k[i][j]%=mo;
        rep(j,i+1,n){
            int mul=k[j][i];
            rep(l,i,numx+1)
                k[j][l]+=mo-mul*k[i][l]%mo,k[j][l]%=mo;
        }
        if(n==1995){puts("!");
        rep(j,1,n){
            rep(l,1,numx+1)
                printf("%lld ",k[j][l]);
            puts("");
        }}
    }
    repp(i,numx,1){
        gres[i]=k[i][numx+1];
        rep(j,i+1,numx)
            gres[i]+=mo-gres[j]*k[i][j]%mo,gres[i]%=mo;
        if(n==1995)printf("gres:%lld %lld\n",i,gres[i]);
    }
}
struct answer{
    int x,y,v;
    friend bool operator<(answer x,answer y){
        if(x.x!=y.x)return x.x<y.x;
        else return x.y<y.y;
    }
};
vector<answer>ans;
signed main(){
    read(n);
    rep(i,1,n){
        rep(j,1,n)
            read(a[i][j]);
    }
    rep(i,1,n){
        rep(j,1,n)
            read(b[i][j]);
    }
    //check columns
    rep(i,1,n)
        rdm[i]=rdn(1,1000000000);
    rep(i,1,n){
        resm[i]=0;
        rep(j,1,n)
            resm[i]+=a[j][i]*rdm[j]%mo,resm[i]%=mo;
    }
    swap(rdm,resm);
    rep(i,1,n){
        int yv=resm[i];
        resm[i]=0;
        rep(j,1,n)
            resm[i]+=b[j][i]*rdm[j]%mo,resm[i]%=mo;
        if(resm[i]!=yv)incl.push_back(i),wrl[i]=1;
    }
    //check rows
    rep(i,1,n)
        rdm[i]=rdn(1,1000000000);
    rep(i,1,n){
        resm[i]=0;
        rep(j,1,n)
            resm[i]+=a[i][j]*rdm[j],resm[i]%=mo;
    }
    swap(rdm,resm);
    rep(i,1,n){
        int yv=resm[i];
        resm[i]=0;
        rep(j,1,n)
            resm[i]+=b[i][j]*rdm[j]%mo,resm[i]%=mo;
        if(resm[i]!=yv)inch.push_back(i),wrh[i]=1;
    }
    //count the answer for each wrong column.
    for(auto nwl:incl){
        rep(i,1,n){
            int cntx=0;
            k[i][inch.size()+1]=(i==nwl);
            rep(j,1,n){
                if(wrh[i])k[i][++cntx]=a[i][j];
                else k[i][inch.size()+1]+=mo-a[i][j]*b[j][nwl]%mo,k[i][inch.size()+1]%=mo;
            }
        }
        if(n==1995){rep(i,1,n){
            rep(j,1,inch.size()+1)
                printf("%lld ",k[i][j]);
            puts("");
        }}
        gauss(inch.size());
        int cntx=0;
        rep(i,1,n){
            if(!wrh[i])continue;
            if(gres[++cntx]!=b[i][nwl])ans.push_back((answer){i,nwl,gres[cntx]});
        }
    }
    sort(ans.begin(),ans.end());
    printf("%lld\n",ans.size());
    for(auto i:ans)
        printf("%lld %lld %lld\n",i.x,i.y,i.v);
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 7884kb

input:

1
953176428
107682094

output:

0

result:

ok single line: '0'

Test #2:

score: -100
Wrong Answer
time: 337ms
memory: 96716kb

input:

1995
586309310 548144807 578573993 437893403 641164340 712256053 172321263 108058526 768610920 123320669 762746291 856047593 979279376 29067913 309867338 292286426 45124325 239705174 675003623 213743652 620561338 116308277 695369179 669459894 682522334 846995555 159510341 999359657 645579085 7499563...

output:

0 0 554460316 
0 0 15137830 
0 0 816259802 
0 0 971480410 
0 0 687712076 
0 0 667526316 
0 0 877159263 
0 0 568733514 
0 0 955539770 
0 0 176190143 
0 0 608581052 
0 0 143039073 
0 0 278494983 
0 0 37077258 
0 0 974660430 
0 0 367400698 
0 0 519160389 
0 0 967813361 
0 0 127488766 
0 0 893417695 
0 ...

result:

wrong answer 1st lines differ - expected: '2', found: '0 0 554460316 '