QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #439558 | #7612. Matrix Inverse | ttest | TL | 11ms | 130740kb | C++14 | 7.0kb | 2024-06-12 10:44:32 | 2024-06-12 10:44:33 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
#define fir first
#define sec second
#define pii pair<int,int>
#define isz(v) (int)(v.size())
using namespace std;
const int maxn=2005;
const int maxs=2005;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
namespace Solve {
struct mint {
int val;
mint():val(0) {}
mint(ll tval) {
if(-mod<=tval&&tval<2*mod) {
if(tval>=mod) {
tval-=mod;
}
if(tval<0) {
tval+=mod;
}
} else {
tval%=mod;
if(tval<0) {
tval+=mod;
}
}
val=tval;
}
mint& operator += (const mint &b) {
val=val+b.val>=mod?val+b.val-mod:val+b.val;
return *this;
}
mint& operator -= (const mint &b) {
val=val-b.val<0?val-b.val+mod:val-b.val;
return *this;
}
mint& operator *= (const mint &b) {
val=1ll*val*b.val>=mod?1ll*val*b.val%mod:val*b.val;
return *this;
}
mint& operator /= (const mint &b) {
*this*=b.inv();
return *this;
}
friend mint operator + (const mint &a,const mint &b) {
mint ans=a;
ans+=b;
return ans;
}
friend mint operator - (const mint &a,const mint &b) {
mint ans=a;
ans-=b;
return ans;
}
friend mint operator * (const mint &a,const mint &b) {
mint ans=a;
ans*=b;
return ans;
}
friend mint operator / (const mint &a,const mint &b) {
mint ans=a;
ans/=b;
return ans;
}
friend bool operator ! (const mint &v) {
return !v.val;
}
friend mint operator - (const mint &v) {
return mod-v;
}
friend mint& operator ++ (mint &v) {
v+=1;
return v;
}
friend mint operator ++ (mint &v,signed _) {
mint t=v;
v+=1;
return t;
}
friend mint& operator -- (mint &v) {
v-=1;
return v;
}
friend mint operator -- (mint &v,signed _) {
mint t=v;
v-=1;
return t;
}
friend bool operator < (const mint &a,const mint &b) {
return a.val<b.val;
}
friend bool operator == (const mint &a,const mint &b) {
return a.val==b.val;
}
friend bool operator != (const mint &a,const mint &b) {
return a.val!=b.val;
}
friend istream& operator >> (istream &is,mint &x) {
ll val;
is>>val;
x=mint(val);
return is;
}
friend ostream& operator << (ostream &os,const mint &x) {
os<<x.val;
return os;
}
mint qpow(ll y) const {
mint x=*this,ans=1;
if(y<0) {
y=-y;
x=inv();
}
while(y) {
if(y&1) {
ans*=x;
}
x*=x;
y>>=1;
}
return ans;
}
mint inv() const {
// mod must be a prime
return qpow(mod-2);
}
mint sqrt() {
mint a=*this;
auto check=[&](mint x) {
return x.qpow((mod-1)/2)==1;
};
static mt19937 rnd(73385);
mint b=rnd()%mod;
while(check(b*b-a)) {
b=rnd()%mod;
}
static mint val=b*b-a;
struct Complex {
mint real,imag;
Complex(mint treal=0,mint timag=0):real(treal),imag(timag) {}
Complex operator * (const Complex &rhs) {
return {real*rhs.real+imag*rhs.imag*val,real*rhs.imag+imag*rhs.real};
}
Complex& operator *= (const Complex &rhs) {
return *this=*this*rhs;
}
};
auto qpow=[&](Complex x,int y) {
Complex ans={1};
while(y) {
if(y&1) {
ans*=x;
}
x*=x;
y>>=1;
}
return ans;
};
mint ans=qpow({b,1},(mod+1)/2).real;
return min(ans,mod-ans);
}
};
mint qpow(mint x,ll y) {
return x.qpow(y);
}
mint inv(mint x) {
return x.inv();
}
struct Matrix {
int n,m;
mint a[maxs][maxs];
Matrix(int tn=0,int tm=0):n(tn),m(tm) {
for(int i=1;i<=n;i++) {
for(int j=1;j<=m;j++) {
a[i][j]=0;
}
}
}
void init(int tn,int tm) {
n=tn,m=tm;
for(int i=1;i<=n;i++) {
for(int j=1;j<=m;j++) {
a[i][j]=0;
}
}
}
void setI() {
for(int i=1;i<=n;i++) {
for(int j=1;j<=n;j++) {
a[i][j]=i==j;
}
}
}
mint* operator [] (const int &x) {
return a[x];
}
const mint* operator [] (const int &x) const {
return a[x];
}
Matrix operator * (const Matrix &rhs) const {
Matrix c(n,rhs.m);
for(int i=1;i<=n;i++) {
for(int k=1;k<=m;k++) {
if(!a[i][k]) {
continue;
}
for(int j=1;j<=rhs.m;j++) {
c[i][j]+=a[i][k]*rhs[k][j];
}
}
}
return c;
}
Matrix qpow(ll y) {
Matrix ans(n,n),x=*this;
ans.setI();
while(y) {
if(y&1) {
ans=ans*x;
}
x=x*x;
y>>=1;
}
return ans;
}
friend ostream& operator << (ostream& os,Matrix t) {
for(int i=1;i<=t.n;i++) {
for(int j=1;j<=t.m;j++) {
os<<t[i][j]<<" ";
}
if(i!=t.n) {
os<<"\n";
}
}
return os;
}
};
Matrix qpow(Matrix x,ll y) {
Matrix ans(x.n,x.n);
ans.setI();
while(y) {
if(y&1) {
ans=ans*x;
}
x=x*x;
y>>=1;
}
return ans;
}
void clear() {
}
mt19937 rnd;
bool r[maxn];
bool c[maxn];
int id[maxn][maxn];
mint e[maxn*13][13*13];
array<int,2> pos[maxn];
int getr(int l,int r) {
return uniform_int_distribution<int>(l,r)(rnd);
}
void main(int tid) {
int n;
cin>>n;
Matrix a(n,n),b(n,n);
for(int i=1;i<=n;i++) {
for(int j=1;j<=n;j++) {
cin>>a[i][j];
}
}
for(int i=1;i<=n;i++) {
for(int j=1;j<=n;j++) {
cin>>b[i][j];
}
}
Matrix u(1,n),v(n,1);
for(int i=1;i<=n;i++) {
u[1][i]=getr(0,mod-1);
v[i][1]=getr(0,mod-1);
}
Matrix cu=(u*a)*b,cv=a*(b*v);
for(int i=1;i<=n;i++) {
if(cu[1][i]!=u[1][i]) {
c[i]=true;
}
if(cv[i][1]!=v[i][1]) {
r[i]=true;
}
}
int cnt=0;
for(int i=1;i<=n;i++) {
for(int j=1;j<=n;j++) {
if(r[i]&&c[j]) {
id[i][j]=++cnt;
pos[cnt]={i,j};
}
}
}
int ec=0;
for(int i=1;i<=n;i++) {
if(c[i]) {
for(int j=1;j<=n;j++) {
ec++;
for(int k=1;k<=n;k++) {
if(id[k][i]) {
e[ec][id[k][i]]+=a[j][k];
} else {
e[ec][cnt+1]-=a[j][k]*b[k][i];
}
}
if(i==j) {
e[ec][cnt+1]++;
}
}
}
}
for(int i=1;i<=cnt;i++) {
int id=i;
for(int j=i;j<=ec;j++) {
if(e[j][i].val) {
id=j;
}
}
for(int j=1;j<=cnt+1;j++) {
swap(e[i][j],e[id][j]);
}
for(int j=1;j<=ec;j++) {
if(i==j) {
continue;
}
mint v=e[j][i]/e[i][i];
for(int k=1;k<=cnt+1;k++) {
e[j][k]-=v*e[i][k];
}
}
}
int cc=0;
for(int i=1;i<=cnt;i++) {
mint res=e[i][cnt+1]/e[i][i];
if(res!=b[pos[i][0]][pos[i][1]]) {
++cc;
}
}
cout<<cc<<"\n";
for(int i=1;i<=cnt;i++) {
mint res=e[i][cnt+1]/e[i][i];
if(res!=b[pos[i][0]][pos[i][1]]) {
cout<<pos[i][0]<<" "<<pos[i][1]<<" "<<res<<"\n";
}
}
}
void init() {
}
}
signed main() {
#ifndef ONLINE_JUDGE
freopen("data.in","r",stdin);
freopen("data.out","w",stdout);
#endif
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int T=1;
// cin>>T;
Solve::init();
for(int t=1;t<=T;t++) {
Solve::main(t);
Solve::clear();
}
}
详细
Test #1:
score: 100
Accepted
time: 11ms
memory: 130740kb
input:
1 953176428 107682094
output:
0
result:
ok single line: '0'
Test #2:
score: -100
Time Limit Exceeded
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...