yukicoder : No.3231 2×2行列相似判定 〜hard〜

なるほど…。
https://yukicoder.me/problems/no/3231

問題

2*2の行列A,Bが与えられる。
正則行列Pのうち、PA≡BP (mod 1000000007)となるものがあるか。

解法

P^-1を両辺の右に掛けると、PAP^(-1)≡Bとなればよい。
A,Bがスカラー行列である場合、条件を満たすのはA≡Bの時だけで、その時P＝E。
いずれもスカラー行列でない場合、AとPAP^(-1)の特性方程式は変わらないため、AとBの特性方程式が一致するなら、適切なPを掛け条件を満たすことが可能。

const ll mo=1000000007;
ll A[2][2],B[2][2];

void yes() {
	cout<<"Yes"<<endl;
	exit(0);
}
void no() {
	cout<<"No"<<endl;
	exit(0);
}
	

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	FOR(y,2) FOR(x,2) cin>>A[y][x];
	FOR(y,2) FOR(x,2) cin>>B[y][x];
	
	FOR(i,4) if(A[i%2][i/2]!=B[i%2][i/2]) break;
	if(i==4) yes();
	if(A[0][0]==A[1][1]&&A[0][1]==0&&A[1][0]==0) no();
	if(B[0][0]==B[1][1]&&B[0][1]==0&&B[1][0]==0) no();
	
	ll ax=((-A[0][0]-A[1][1])%mo+mo)%mo;
	ll bx=((-B[0][0]-B[1][1])%mo+mo)%mo;
	ll a=((A[0][0]*A[1][1]-A[0][1]*A[1][0])%mo+mo)%mo;
	ll b=((B[0][0]*B[1][1]-B[0][1]*B[1][0])%mo+mo)%mo;
	if(ax==bx&&a==b) yes();
	no();
	
	
}

まとめ

もっとBSGSとか使うかと思ってしまった。