Submission #2150669

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
using Int = long long;

const Int MOD=1e9+9; //<- alert!!!
typedef vector<Int> arr;
typedef vector<arr> mat;
inline arr mul(const mat &a,arr &b,Int mod){
  arr res(b.size(),0);
  for(Int i=0;i<(Int)b.size();i++)
    for(Int j=0;j<(Int)a[i].size();j++)
      (res[i]+=a[i][j]*b[j])%=mod;
  return res;
}
inline mat mul(const mat &a,const mat &b,Int mod){
  mat res(a.size(),arr(b[0].size(),0));
  for(Int i=0;i<(Int)a.size();i++)
    for(Int j=0;j<(Int)b[0].size();j++)
      for(Int k=0;k<(Int)b.size();k++)
	(res[i][j]+=a[i][k]*b[k][j])%=mod;
  return res;
}
inline mat mat_pow(mat a,Int n,Int mod){
  mat res(a);
  for(Int i=0;i<(Int)a.size();i++)
    for(Int j=0;j<(Int)a[i].size();j++)
      res[i][j]=(i==j);
  while(n){
    if(n&1) res=mul(a,res,mod);
    a=mul(a,a,mod);
    n>>=1;
  }
  return res;
}

//INSERT ABOVE HERE
signed main(){
  Int n;
  cin>>n;
  mat A(n,arr(n,0));
  for(Int i=0;i<n;i++)
    for(Int j=0;j<n;j++)
      cin>>A[i][j];
  mat B(n,arr(n,0));
  for(Int i=0;i<n;i++)
    for(Int j=0;j<n;j++)
      cin>>B[i][j];
  mat C(n,arr(n,0));
  for(Int i=0;i<n;i++)
    for(Int j=0;j<n;j++)
      cin>>C[i][j];

  
  for(Int i=0;i<n;i++){
    for(Int j=0;j<n;j++){
      while(A[i][j]<0) A[i][j]+=MOD;
      while(B[i][j]<0) B[i][j]+=MOD;
      while(C[i][j]<0) C[i][j]+=MOD;
    }
  }
  
  auto start=clock();
  random_device rd;
  mt19937 mt(rd());
  while(double(clock()-start)/CLOCKS_PER_SEC<4.0){
    arr x(n);
    for(Int i=0;i<n;i++) x[i]=mt()%MOD;
    auto y=mul(B,x,MOD);
    auto z=mul(A,y,MOD);
    auto p=mul(C,x,MOD);
    for(Int i=0;i<n;i++){
      if(z[i]!=p[i]){
	//cout<<z[i]<<" "<<p[i]<<endl;
	cout<<"NO"<<endl;
	return 0;
      }
    }
  }
  cout<<"YES"<<endl;
  return 0;
}

Submission Info

Judge Result