結果

問題 No.3225 2×2行列相似判定 〜easy〜
コンテスト
ユーザー Carpenters-Cat
提出日時 2025-08-12 00:59:54
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,554 bytes
コンパイル時間 1,892 ms
コンパイル使用メモリ 201,268 KB
実行使用メモリ 7,720 KB
最終ジャッジ日時 2025-08-12 00:59:58
合計ジャッジ時間 3,514 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2 WA * 1
other AC * 1 WA * 32
権限があれば一括ダウンロードができます

ソースコード

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];
			}
		}
	}
	for (auto& a : X) {
		for (auto& b : a) {
			b += p * p;
			b %= p;
		}
	}
	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 (r < 4 && (X[r][i] == 0)) r ++;
		if (r == 4) {
			puts("No");
			return 0;
		}
		int b = X[r][i];
		for (int j = 3; j >= i; j --) {
			swap(X[i][j], X[r][j]);
			X[i][j] = (X[i][j] * iv[b]) % p;
		}
		for (int x = 0; x < 4; x ++) {
			if (x == i) continue;
			for (int j = 3; j >= i; j --) {
				X[x][j] -= X[x][i] * X[i][j];
				if (X[x][j] < 0) {
					X[x][j] = (-X[x][j]) % p;
					X[x][j] = p - X[x][j];
				}
				X[x][j] %= p;
			}
		}
	}
	puts("Yes");
}
0