QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#743037 | #7612. Matrix Inverse | yanshanjiahong | WA | 337ms | 96716kb | C++23 | 3.8kb | 2024-11-13 18:01:22 | 2024-11-13 18:01:22 |
Judging History
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 '