QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#743013 | #7612. Matrix Inverse | yanshanjiahong | WA | 319ms | 97836kb | C++23 | 3.4kb | 2024-11-13 17:56:18 | 2024-11-13 17:56:23 |
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);
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;
}
}
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;
}
}
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;
}
}
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;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 8032kb
input:
1 953176428 107682094
output:
0
result:
ok single line: '0'
Test #2:
score: -100
Wrong Answer
time: 319ms
memory: 97836kb
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:
4 827 238 695464888 827 499 695464888 1466 238 215406555 1466 499 215406555
result:
wrong answer 1st lines differ - expected: '2', found: '4'