結果
問題 |
No.3225 2×2行列相似判定 〜easy〜
|
ユーザー |
![]() |
提出日時 | 2025-08-08 23:42:15 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,399 bytes |
コンパイル時間 | 2,824 ms |
コンパイル使用メモリ | 287,392 KB |
実行使用メモリ | 15,936 KB |
最終ジャッジ日時 | 2025-08-08 23:42:22 |
合計ジャッジ時間 | 6,258 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 TLE * 1 -- * 1 |
other | -- * 33 |
ソースコード
#include<bits/stdc++.h> using namespace std; struct matrix{ using T=long long; int h,w; vector<vector<T>> val; matrix(int r,int c=-1):h(r),w(c){ if (w==-1) w=h; val.assign(h,vector<T>(w,0)); } matrix operator*(matrix b){ matrix a=*this,c(h,b.w); for (int i=0;i<h;i++){ for (int j=0;j<b.w;j++){ for (int k=0;k<w;k++){ c.val[i][j]+=a.val[i][k]*b.val[k][j]; } } } return c; } matrix identity(int n){ matrix ret(n,n); for (int i=0;i<n;i++) ret.val[i][i]=1; return ret; } matrix pow(long long k){ matrix ret(h,w),m=*this; ret=ret.identity(h); while (k>0){ if (k%2==1) ret=ret*m; m=m*m; k/=2; } return ret; } }; int main(){ int p=67; int n=2; matrix a(n),b(n); for (int i=0;i<n;i++) for (int j=0;j<n;j++) cin>>a.val[i][j]; for (int i=0;i<n;i++) for (int j=0;j<n;j++) cin>>b.val[i][j]; matrix P(n); for (int x1=0;x1<p;x1++) for (int x2=0;x2<p;x2++) for (int x3=0;x3<p;x3++) for (int x4=0;x4<p;x4++){ P.val[0][0]=x1; P.val[0][1]=x2; P.val[1][0]=x3; P.val[1][1]=x4; matrix ma=P*a,mb=b*P; bool ok=(x1*x4-x2*x3)%p; for (int i=0;i<n;i++) for (int j=0;j<n;j++){ if (ma.val[i][j]%p!=mb.val[i][j]%p){ ok=false; break; } } if (ok){ cout<<"Yes\n"; return 0; } } cout<<"No\n"; }