結果

問題 No.3225 2×2行列相似判定 〜easy〜
ユーザー Carpenters-Cat
提出日時 2025-08-11 05:10:26
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
RE  
実行時間 -
コード長 1,453 bytes
コンパイル時間 1,856 ms
コンパイル使用メモリ 201,460 KB
実行使用メモリ 7,720 KB
最終ジャッジ日時 2025-08-11 05:10:35
合計ジャッジ時間 7,267 ms
ジャッジサーバーID
(参考情報)
judge3 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample RE * 3
other RE * 33
権限があれば一括ダウンロードができます

ソースコード

diff #

#include <bits/stdc++.h>
using namespace std;
using vc = std::vector<int> ;
using mat = vector<vc>;
const int p = 67;
mat prod(const mat& A, const mat& B) {
	mat ret(A.size(), vc(B[0].size()));
	for (int i = 0; i < A.size(); i ++) {
		for (int j = 0; j < B[0].size(); j ++) {
			ret[i][j] = 0;
			for (int k = 0; k < A[0].size(); k ++) {
				ret[i][j] += A[i][k] * B[k][j];
			}
		}
	}
	return ret;
}
int main () {
	mat A(2, vc(2)), B(2, vc(2));
	for (auto& a : A) {
		for (auto& b : a) {
			cin >> b;
		}
	}
	for (auto& a : B) {
		for (auto& b : a) {
			cin >> b;
		}
	}
	mat X(4, vc(4, 0));
	for (int i = 0; i < 2; i ++) {
		for (int j = 0; j < 2; j ++) {
			for (int k = 0; k < 2; k ++) {
				int p = i * 2 + j;
				int q = i * 2 + k;
				int r = k * 2 + j;
				X[p][q] += A[k][j];
				X[p][r] -= B[i][k];
			}
		}
	}
	vc iv(p, 0);
	for (int i = 1; i < p; i ++) {
		for (int j = 1; j < p; j ++) {
			if ((i * j) % p == 1) {
				iv[i] = j; iv[j] = i;
			}
		}
	}
	for (int i = 0; i < 4; i ++) {
		int r = i;
		while (A[r][i] == 0) r ++;
		if (r == 4) {
			puts("No");
			return 0;
		}
		for (int j = 0; j < 4; j ++) {
			swap(A[i][j], A[r][j]);
			A[i][j] = (A[i][j] * iv[A[i][j]]) % p;
		}
		for (int x = 0; x < 4; x ++) {
			if (x == i) continue;
			for (int j = 3; j >= i; j --) {
				A[x][j] -= A[x][i] * A[i][j];
				if (A[x][j] < 0) {
					A[x][j] = (-A[x][j]) % p;
					A[x][j] = p - A[x][j];
				}
				A[x][j] %= p;
			}
		}
	}
	puts("Yes");
}
0