結果
問題 |
No.3225 2×2行列相似判定 〜easy〜
|
ユーザー |
![]() |
提出日時 | 2025-08-08 23:49:52 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 427 ms / 2,000 ms |
コード長 | 1,418 bytes |
コンパイル時間 | 3,259 ms |
コンパイル使用メモリ | 279,108 KB |
実行使用メモリ | 7,720 KB |
最終ジャッジ日時 | 2025-08-08 23:50:03 |
合計ジャッジ時間 | 11,068 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 33 |
ソースコード
#include<bits/stdc++.h> using namespace std; struct matrix{ using T=long long; int h,w; int val[2][2]; matrix(int r,int c=-1):h(r),w(c){ if (w==-1) w=h; for (int i=0;i<2;i++) for (int j=0;j<2;j++) val[i][j]=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"; }