結果

問題 No.3225 2×2行列相似判定 〜easy〜
ユーザー kwm_t
提出日時 2025-08-08 21:43:39
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 3,781 bytes
コンパイル時間 5,924 ms
コンパイル使用メモリ 335,520 KB
実行使用メモリ 7,716 KB
最終ジャッジ日時 2025-08-08 21:43:55
合計ジャッジ時間 9,105 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1 TLE * 1 -- * 1
other -- * 33
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
using mint = atcoder::modint;
//using mint = modint1000000007;
//const int mod = 1000000007;
//using mint = modint998244353;
//const int mod = 998244353;
//const int INF = 1e9;
//const long long LINF = 1e18;
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep2(i,l,r)for(int i=(l);i<(r);++i)
#define rrep(i, n) for (int i = (n) - 1; i >= 0; --i)
#define rrep2(i,l,r)for(int i=(r) - 1;i>=(l);--i)
#define all(x) (x).begin(),(x).end()
#define allR(x) (x).rbegin(),(x).rend()
#define P pair<int,int>
template<typename A, typename B> inline bool chmax(A & a, const B & b) { if (a < b) { a = b; return true; } return false; }
template<typename A, typename B> inline bool chmin(A & a, const B & b) { if (a > b) { a = b; return true; } return false; }
template<typename T>
struct Matrix {
	int row, column;
	std::vector<std::vector<T>>mat;
	Matrix(int r = 0, int c = 0, T val = 0) :row(r), column(c) {
		mat = std::vector<std::vector<T>>(row, std::vector<T>(column, val));
	}
	std::vector<T>& operator[](const int i) {
		return mat[i];
	}
	Matrix& operator+=(const Matrix & other) {
		assert(row == other.row && column == other.column);
		for (int i = 0; i < row; ++i) {
			for (int j = 0; j < column; ++j) {
				mat[i][j] += other.mat[i][j];
			}
		}
		return *this;
	}
	Matrix& operator-=(const Matrix & other) {
		assert(row == other.row && column == other.column);
		for (int i = 0; i < row; ++i) {
			for (int j = 0; j < column; ++j) {
				mat[i][j] -= other.mat[i][j];
			}
		}
		return *this;
	}
	Matrix& operator*=(const Matrix & other) {
		assert(column == other.row);
		Matrix ret(row, other.column);
		for (int i = 0; i < row; ++i) {
			for (int k = 0; k < column; ++k) {
				for (int j = 0; j < other.column; ++j) {
					ret.mat[i][j] += mat[i][k] * other.mat[k][j];
				}
			}
		}
		return *this = ret;
	}
	Matrix& operator*=(T k) {
		for (int i = 0; i < row; ++i) {
			for (int j = 0; j < column; ++j) {
				mat[i][j] *= k;
			}
		}
		return *this;
	}
	Matrix operator+(const Matrix other)const { return Matrix(*this) += other; }
	Matrix operator-(const Matrix other)const { return Matrix(*this) -= other; }
	Matrix operator*(const Matrix other)const { return Matrix(*this) *= other; }
	Matrix operator*(const T k)const { return Matrix(*this) *= k; }
	std::vector<T> operator*(const std::vector<T> other) const {
		assert(column == (int)other.size());
		std::vector<T> ret(row);
		for (int i = 0; i < row; ++i) {
			for (int j = 0; j < column; ++j) {
				ret[i] += mat[i][j] * other[j];
			}
		}
		return ret;
	}
	Matrix pow(long long n) const {
		assert(row == column);
		if (n == 0) {
			Matrix e(row, column);
			for (int i = 0; i < row; ++i) e.mat[i][i] = 1;
			return e;
		}
		Matrix ret = pow(n >> 1);
		ret *= ret;
		if (n & 1) ret *= *this;
		return ret;
	}
	Matrix debug() {
		for (int i = 0; i < row; ++i) {
			for (int j = 0; j < column; ++j) std::cout << mat[i][j] << " ";
			std::cout << std::endl;
		}
	}
};
int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	mint::set_mod(67);
	int a, b, c, d; cin >> a >> b >> c >> d;
	Matrix<mint> mat(2, 2, 0);
	mat[0][0] = a;
	mat[0][1] = b;
	mat[1][0] = c;
	mat[1][1] = d;
	cin >> a >> b >> c >> d;
	Matrix<mint> mat2(2, 2, 0);
	mat2[0][0] = a;
	mat2[0][1] = b;
	mat2[1][0] = c;
	mat2[1][1] = d;
	Matrix<mint> mat3(2, 2, 0);
	rep(i, 67)rep(j, 67)rep(k, 67)rep(l, 67) {
		if (!(i * l - j * k) % 67)continue;
		mat3[0][0] = i;
		mat3[0][1] = j;
		mat3[1][0] = k;
		mat3[1][1] = l;
		auto x = mat3 * mat;
		auto y = mat2 * mat3;
		bool chk = true;
		rep(i, 2)rep(j, 2) if (x[i][j] != y[i][j])chk = false;
		if (chk) {
			cout << "Yes" << endl;
			return 0;
		}
	}
	cout << "No" << endl;
	return 0;
}
0