結果
| 問題 |
No.3225 2×2行列相似判定 〜easy〜
|
| ユーザー |
 こめだわら
|
| 提出日時 | 2025-08-08 21:57:13 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 2 ms / 2,000 ms |
| コード長 | 9,689 bytes |
| コンパイル時間 | 3,013 ms |
| コンパイル使用メモリ | 284,360 KB |
| 実行使用メモリ | 7,716 KB |
| 最終ジャッジ日時 | 2025-08-08 21:57:20 |
| 合計ジャッジ時間 | 4,189 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 33 |
ソースコード
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
#define rep(i,n) for(ll i=0;i<n;++i)
#define all(a) (a).begin(),(a).end()
ll intpow(ll a, ll b){ ll ans = 1; while(b){ if(b & 1) ans *= a; a *= a; b /= 2; } return ans; }
ll modpow(ll a, ll b, ll p){ ll ans = 1; while(b){ if(b & 1) (ans *= a) %= p; (a *= a) %= p; b /= 2; } return ans; }
template<class T> T div_floor(T a, T b) { return a / b - ((a ^ b) < 0 && a % b); }
template<class T> T div_ceil(T a, T b) { return a / b + ((a ^ b) > 0 && a % b); }
template <typename T, typename U> inline bool chmin(T &x, U y) { return (y < x) ? (x = y, true) : false; }
template <typename T, typename U> inline bool chmax(T &x, U y) { return (x < y) ? (x = y, true) : false; }
namespace noya2 {
template<typename T, size_t hw = -1uz>
struct matrix {
static constexpr int h = hw, w = hw;
std::array<T, hw*hw> m;
matrix () : m({}) {}
matrix (const std::array<T, hw*hw> &_m) : m(_m) {}
matrix (const std::array<std::array<T, hw>, hw> &_m){
for (int i = 0; i < h; i++) for (int j = 0; j < w; j++){
m[idx(i,j)] = _m[i][j];
}
}
matrix (const std::vector<std::vector<T>> &_m){
for (int i = 0; i < h; i++) for (int j = 0; j < w; j++){
m[idx(i,j)] = _m[i][j];
}
}
auto operator[](int i) const {
return std::ranges::subrange(m.begin()+i*w,m.begin()+(i+1)*w);
}
auto operator[](int i){
return std::ranges::subrange(m.begin()+i*w,m.begin()+(i+1)*w);
}
matrix &operator+= (const matrix &r){
for (int i = 0; i < h; ++i){
for (int j = 0; j < w; ++j){
m[idx(i,j)] += r.m[idx(i,j)];
}
}
return *this;
}
matrix &operator-= (const matrix &r){
for (int i = 0; i < h; ++i){
for (int j = 0; j < w; ++j){
m[idx(i,j)] -= r.m[idx(i,j)];
}
}
return *this;
}
matrix &operator*= (const matrix &r){
matrix ret;
for (int i = 0; i < h; i++){
for (int k = 0; k < w; k++){
for (int j = 0; j < r.w; j++){
ret.m[idx(i,j)] += m[idx(i,k)] * r.m[idx(k,j)];
}
}
}
return *this = ret;
}
matrix operator+ (const matrix &r) const { return matrix(*this) += r; }
matrix operator- (const matrix &r) const { return matrix(*this) -= r; }
matrix operator* (const matrix &r) const { return matrix(*this) *= r; }
matrix& operator*=(const T &r){
for (int i = 0; i < h; ++i){
for (int j = 0; j < w; ++j){
m[idx(i,j)] *= r;
}
}
return *this;
}
friend matrix operator* (const T &r, const matrix &mat){
return matrix(mat) *= r;
}
friend matrix operator* (const matrix &mat, const T &r){
return matrix(mat) *= r;
}
matrix pow(long long n){
if (n == 0) return e();
matrix f = pow(n / 2);
matrix ret = f * f;
if (n & 1) ret *= (*this);
return ret;
}
int idx(int i, int j){
return i * w + j;
}
static matrix e(){
matrix ret;
for (int i = 0; i < h; i++){
ret[i][i] = T(1);
}
return ret;
}
friend std::ostream &operator<<(std::ostream &os, const matrix &mat){
for (int i = 0; i < mat.h; i++){
if (i != 0) os << '\n';
for (int j = 0; j < mat.w; j++){
if (j != 0) os << ' ';
os << mat[i][j];
}
}
return os;
}
friend std::istream &operator>>(std::istream &is, matrix &mat){
for (int i = 0; i < mat.h; i++){
for (int j = 0; j < mat.w; j++){
is >> mat[i][j];
}
}
return is;
}
friend bool operator==(const matrix &a, const matrix &b){
for (int i = 0; i < a.h; i++){
for (int j = 0; j < a.w; j++){
if (a[i][j] != b[i][j]){
return false;
}
}
}
return true;
}
};
template<typename T>
struct matrix<T,-1uz> {
int h, w;
std::vector<T> m;
matrix () {}
matrix (int _h) : matrix(_h,_h) {}
matrix (int _h, int _w) : h(_h), w(_w), m(_h*_w) {}
matrix (int _h, int _w, const std::vector<T> &_m) : h(_h), w(_w), m(_m) {
assert((int)_m.size() == _h*_w);
}
matrix (const std::vector<std::vector<T>> &_m){
h = _m.size();
assert(h >= 1);
w = _m[0].size();
for (int i = 0; i < h; i++) for (int j = 0; j < w; j++){
m[idx(i,j)] = _m[i][j];
}
}
auto operator[](int i) const {
return std::ranges::subrange(m.begin()+i*w,m.begin()+(i+1)*w);
}
auto operator[](int i){
return std::ranges::subrange(m.begin()+i*w,m.begin()+(i+1)*w);
}
matrix &operator+= (const matrix &r){
for (int i = 0; i < h; ++i){
for (int j = 0; j < w; ++j){
m[idx(i,j)] += r.m[idx(i,j)];
}
}
return *this;
}
matrix &operator-= (const matrix &r){
for (int i = 0; i < h; ++i){
for (int j = 0; j < w; ++j){
m[idx(i,j)] -= r.m[idx(i,j)];
}
}
return *this;
}
matrix &operator*= (const matrix &r){
matrix ret(h, r.w);
for (int i = 0; i < h; i++){
for (int k = 0; k < w; k++){
for (int j = 0; j < r.w; j++){
ret.m[idx(i,j)] += m[idx(i,k)] * r.m[idx(k,j)];
}
}
}
return *this = ret;
}
matrix operator+ (const matrix &r) const { return matrix(*this) += r; }
matrix operator- (const matrix &r) const { return matrix(*this) -= r; }
matrix operator* (const matrix &r) const { return matrix(*this) *= r; }
matrix& operator*=(const T &r){
for (int i = 0; i < h; ++i){
for (int j = 0; j < w; ++j){
m[idx(i,j)] *= r;
}
}
return *this;
}
friend matrix operator* (const T &r, const matrix &mat){
return matrix(mat) *= r;
}
friend matrix operator* (const matrix &mat, const T &r){
return matrix(mat) *= r;
}
matrix pow(long long n){
if (n == 0) return e(h);
matrix f = pow(n / 2);
matrix ret = f * f;
if (n & 1) ret *= (*this);
return ret;
}
int idx(int i, int j){
return i * w + j;
}
static matrix e(int _h){
auto ret = matrix(_h, _h);
for (int i = 0; i < _h; i++){
ret[i][i] = T(1);
}
return ret;
}
friend std::ostream &operator<<(std::ostream &os, const matrix &mat){
for (int i = 0; i < mat.h; i++){
if (i != 0) os << '\n';
for (int j = 0; j < mat.w; j++){
if (j != 0) os << ' ';
os << mat[i][j];
}
}
return os;
}
friend std::istream &operator>>(std::istream &is, matrix &mat){
for (int i = 0; i < mat.h; i++){
for (int j = 0; j < mat.w; j++){
is >> mat[i][j];
}
}
return is;
}
};
template<typename T, size_t _hw = -1uz>
T determinant(matrix<T, _hw> mat){
int hw = mat.h;
T ret = 1;
for (int i = 0; i < hw; i++) {
int idx = -1;
for (int j = i; j < hw; j++) {
if (mat[j][i] != 0) {
idx = j;
break;
}
}
if (idx == -1) return 0;
if (i != idx) {
ret *= T(-1);
for (int j = 0; j < hw; j++){
std::swap(mat[i][j],mat[idx][j]);
}
}
ret *= mat[i][i];
T inv = T(1) / mat[i][i];
for (int j = 0; j < hw; j++) {
mat[i][j] *= inv;
}
for (int j = i + 1; j < hw; j++) {
T a = mat[j][i];
if (a == 0) continue;
for (int k = i; k < hw; k++) {
mat[j][k] -= mat[i][k] * a;
}
}
}
return ret;
}
} // namespace noya2
using namespace noya2;
void solve() {
matrix<ll> A(2,2),B(2,2);
rep(i,2)rep(j,2)cin>>A[i][j];
rep(i,2)rep(j,2)cin>>B[i][j];
const ll mod=67;
bool flag=true;
rep(i,2)rep(j,2){
if (A[i][j]!=B[i][j]){
flag=false;
}
}
if (flag){
cout<<"Yes"<<endl;
return;
}
flag=true;
rep(i,2)rep(j,2){
if (A[i][j]!=0){
flag=false;
}
}
if (flag){
cout<<"No"<<endl;
return;
}
flag=true;
rep(i,2)rep(j,2){
if (B[i][j]!=0){
flag=false;
}
}
if (flag){
cout<<"No"<<endl;
return;
}
flag=true;
if (A[0][0]!=A[1][1]){
flag=false;
}
if (A[0][1]!=0 or A[1][0]!=0){
flag=false;
}
if (flag){
cout<<"No"<<endl;
return;
}
flag=true;
if (B[0][0]!=B[1][1]){
flag=false;
}
if (B[0][1]!=0 or B[1][0]!=0){
flag=false;
}
if (flag){
cout<<"No"<<endl;
return;
}
ll da=A[0][0]*A[1][1]-A[0][1]*A[1][0];
ll ta=0;
rep(i,2)ta+=A[i][i];
ll db=B[0][0]*B[1][1]-B[0][1]*B[1][0];
ll tb=0;
rep(i,2)tb+=B[i][i];
if ((da-db)%mod==0 and (ta-tb)%mod==0){
cout<<"Yes"<<endl;
}
else{
cout<<"No"<<endl;
}
return;
}
int main() {
ll T=1;
while (T--){
solve();
}
return 0;
}